F. Dark Matter Purification
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Deep within the ancient ruins of Astra, young explorer A discovered a core matrix severely eroded by dark matter. This matrix can be regarded as a row of $$$n$$$ energy nodes, numbered from 1 to $$$n$$$.

The defense system of the ruins is attempting to purify these nodes. Due to the damage to the system, it can only perform random purification operations. Specifically, in every second, the defense system will randomly select one interval (with equal probability) from all possible consecutive subintervals $$$[L, R]$$$ ($$$1 \le L \le R \le n$$$) and release a beam of purification light, purifying all the nodes within that interval once. There are a total of $$$\frac{n(n+1)}{2}$$$ possible choices.

Please note that it is permitted and harmless for the same node to be purified multiple times.

Little A wants to know: starting from the moment the defense system is activated, until all $$$n$$$ nodes have been purified at least once, what is the average number of seconds required?

Since the expected value might be a fraction, please output the result of this fraction modulo $$$10^9 + 7$$$. Specifically, if the simplest fraction for the expected value is $$$\frac{P}{Q}$$$, you need to output an integer $$$X$$$ such that $$$X \cdot Q \equiv P \pmod{10^9 + 7}$$$ and $$$0 \le X \lt 10^9 + 7$$$.

Input

The input consists of only one line with a single integer $$$n$$$ ($$$1 \le n \le 100$$$), representing the number of energy nodes.

Output

Output an integer representing the result of the expected seconds modulo $$$10^9 + 7$$$.

Examples
Input
1
Output
1
Input
2
Output
2
Input
3
Output
300000005
Note

For the case where $$$n=2$$$, all possible intervals are $$$[1, 1], [2, 2], [1, 2]$$$, totaling $$$3$$$ types. Each type has a probability of $$$\frac{1}{3}$$$ of being selected.

  • If $$$[1, 2]$$$ is selected in the first second, both nodes will be purified, and it will take 1 second.
  • If $$$[1, 1]$$$ is selected in the first second, then we need to wait for the selection of the interval containing node 2 (i.e., $$$[2, 2]$$$ or $$$[1, 2]$$$). After that, each time there is a $$$\frac{2}{3}$$$ probability of selecting the target interval, and the expected additional time is $$$\frac{3}{2} = 1.5$$$ seconds. Thus, the total expected time is $$$1 + 1.5 = 2.5$$$ seconds.
  • If $$$[2, 2]$$$ is selected in the first second, similarly, the total expected time is 2.5 seconds.

Overall, the total expected time is $$$\frac{1}{3} \times 1 + \frac{1}{3} \times 2.5 + \frac{1}{3} \times 2.5 = 2$$$ seconds.

For the case where $$$n=3$$$, the actual expected number of seconds for purifying all nodes is $$$\frac{29}{10}$$$, which is equivalent to $$$300000005$$$ modulo $$$10^9 + 7$$$.