Problem Statement

For multiple zeta values, please refer to the following page.

https://ja.wikipedia.org/wiki/%E5%A4%9A%E9%87%8D%E3%82%BC%E3%83%BC%E3%82%BF%E5%80%A4

However, in the definition of multiple zeta values, the elements of the index are real numbers greater than or equal to $1$.

When $a$ is a real number greater than $1$ and $n$ is an integer greater than or equal to $2$, we define $S_{n,a}$ as
the sequence consisting of the products of zeta values, chosen from the zeta values of depth $1$ whose indices are all multiples of $a$ so that the weight is $na$,
and we denote the $i$-th element of $S_{n,a}$ by $(S_{n,a})_i$.
Here, it is guaranteed that the length of $S_{n,a}$ is $p(n)$ (the partition number of $n$).

• ex: $S_{4,2}=$ { $ζ(2)^4,ζ(4)ζ(2)^2,ζ(6)ζ(2),ζ(4)^2,ζ(8)$ }

• For every real number $y$ greater than $1$, \( \displaystyle \sum_{i=1}^{p(x)} (S_{x,y})_i×f_i \) $=ζ(y,y,...,y)(y$ appearing $x$ times) (21:54: corrected $S_{y,x}$ to $S_{x,y}$.)
• \( \displaystyle \sum_{i=1}^{p(x)} f_i=0 \)

Input

$x$

• All inputs are integers.
• $2 \le x \le 8$

Output

For each possible $f$, multiply the product of all its elements by $x!^{p(x)}$, and output the sum of these values modulo $1000000007$.

Sample

2

1000000006