import java.util.Arrays; import java.util.Scanner; class Main { public static void main(String[] args) throws Exception { Scanner sc=new Scanner(System.in); int M=sc.nextInt(); new Main().run(M); } static long MODULO=(long)1e9+7; long pow(long a,long n) { n=(n%(MODULO-1)+(MODULO-1))%(MODULO-1); long ret=1; for(;n>0;n>>=1,a=a*a%MODULO)if(n%2==1)ret=ret*a%MODULO; return ret; } long inv(long a) { return pow(a,MODULO-2); } long solve(long p,int e) { long[][][] dp=new long[e+1][e+2][e+1]; dp[0][e+1][0]=1; for(int sumKU=0;sumKU=1;--k) { for(int sumU=0;sumU=1;--nk) { for(int nu=1;sumKU+nk*nu<=e;++nu) { //(Z/p^nk)^nu long add=pow(p,nk*nu*sumU); for(int m=0;m0) ans=ans*solve(div,e)%MODULO; } ans=ans*fac%MODULO; System.out.println(ans); } // return F^n(0) long factorial(long N) { build(MODULO); long v = (long) Math.sqrt(N); int m = 0; long[][][] f = new long[m + 1][][]; for (int i = 0; i <= m; ++i) { f[i] = F(m, i * v, N); } for (int bit = 63; bit >= 0; --bit) { if (m > 0) { // m -> 2m long[][][] fs = Arrays.copyOfRange(matshift(f, v, m * inv(v, MODULO) % MODULO), m + 1, 2 * m + 2); f = matshift(f, v, f.length); // length: m + 1 -> 2m + 2 fs = matshift(fs, v, fs.length); // length: m + 1 -> 2m + 2 m *= 2; long[][][] f2 = new long[m + 1][][]; for (int i = 0; i <= m; ++i) { f2[i] = matmul(fs[i], f[i]); } f = f2; } if (((1L << bit) & v) > 0) { // m -> m + 1 ++m; long[][][] f2 = new long[m + 1][][]; for (int i = 0; i < m; ++i) { f2[i] = matmul(f(m, v * i, N), f[i]); } f2[m] = F(m, m * v, N); f = f2; } } long[][] ret = new long[][] { { 1, 0 }, { 0, 1 } }; for (int i = 0; i <= v - 1; ++i) { ret = matmul(f[i], ret); } for (long i = v * v + 1; i <= N; ++i) { ret = matmul(f(i, 0, N), ret); } return ret[0][0]; } long[][] f(long k, long x, long N) { long[][] ret = new long[][] { { x+k, 0}, { 0, 0} }; if (ret[0][1] >= MODULO) ret[0][1] -= MODULO; if (ret[1][1] >= MODULO) ret[1][1] -= MODULO; return ret; } long[][] F(long n, long x, long N) { long[][] ret = new long[][] { { 1, 0 }, { 0, 1 } }; for (int i = 1; i <= n; ++i) { ret = matmul(f(i, x, N), ret); } return ret; } // m : degree of polynomial // // Converting // from // f[0], f[v] , f[2v] , ..., f[mv] // to // f[0], f[v] , f[2v] , ..., f[mv], f[shift*v], f[shift*v + v] ,f[shift*v + mv] // . // // See f as f(x) = f[x*v]. long[][][] matshift(long[][][] h, long v, long shift) { long[] a0 = new long[h.length]; for (int i = 0; i < h.length; ++i) { a0[i] = h[i][0][0]; } a0 = shift(a0, v, shift); long[][][] ret = new long[a0.length][2][2]; for (int i = 0; i < ret.length; ++i) { ret[i] = new long[][] { { a0[i], 0 }, { 0, 0 } }; } return ret; } long[] shift(long[] h, long v, long shift) { int degree = h.length - 1; long[] a = new long[degree + 1]; long[] b = new long[2 * degree + 1]; long[] ret = new long[2 * h.length]; for (int i = 0; i < h.length; ++i) { ret[i] = h[i]; } long prd = 1; for (int i = 0; i <= degree; ++i) { a[i] = h[i] * ifac[i] % MODULO * ifac[degree - i] % MODULO * ((degree - i) % 2 == 0 ? 1 : -1); if (a[i] < 0) a[i] += MODULO; } for (int i = 0; i <= 2 * degree; ++i) b[i] = inv(shift - degree + i, MODULO); long[] c = middle_product(a, b, MODULO); for (int i = 0; i <= degree; ++i) { prd = prd * (shift - i == 0 ? 1 : (shift - i)) % MODULO; if (prd < 0) prd += MODULO; } for (int i = 0; i < h.length; ++i) { ret[i + h.length] = prd * c[i] % MODULO; prd = prd * (shift + i + 1) % MODULO * inv(shift + i - degree, MODULO) % MODULO; if (prd < 0) prd += MODULO; } if (0 <= shift && shift <= degree) { for (int i = 0; i + shift < h.length; ++i) { ret[i + h.length] = h[i + (int) shift]; } } return ret; } long[][] matmul(long[][] a, long[][] b) { long[][] ret = new long[a.length][b[0].length]; for (int i = 0; i < a.length; ++i) { for (int j = 0; j < b[i].length; ++j) { for (int k = 0; k < a[i].length; ++k) { ret[i][j] += a[i][k] * b[k][j] % MODULO; if (ret[i][j] >= MODULO) ret[i][j] -= MODULO; } } } return ret; } // inv[0] := 1 long inv(long a, long mod) { a %= mod; if (a < 0) a += mod; if (a == 0) { throw new AssertionError(); // return 1; } long b = mod; long p = 1, q = 0; while (b > 0) { long c = a / b; long d; d = a; a = b; b = d % b; d = p; p = q; q = d - c * q; } long ret = p < 0 ? (p + mod) : p; return ret; } final int MAX = 112345; long[] fac = new long[MAX]; long[] ifac = new long[MAX]; long[] inv = new long[MAX]; void build(long MOD) { fac[0] = ifac[0] = inv[0] = fac[1] = ifac[1] = inv[1] = 1; for (int i = 2; i < fac.length; ++i) { fac[i] = fac[i - 1] * i % MOD; inv[i] = MOD - inv[(int) (MOD % i)] * (MOD / i) % MOD; ifac[i] = inv[i] * ifac[i - 1] % MOD; } } long[] middle_product(long[] a, long[] b, long mod0) { long[] MOD = new long[] { 1012924417, 1224736769, 1007681537 }; long[] gen = new long[] { 5, 3, 3 }; long[][] c = new long[3][]; for (int i = 0; i < 3; ++i) { c[i] = middle_product_(Arrays.copyOf(a, a.length), Arrays.copyOf(b, b.length), MOD[i], gen[i]); } for (int i = 0; i < c[0].length; ++i) { c[0][i] = garner(new long[] { c[0][i], c[1][i], c[2][i] }, MOD, mod0); } return c[0]; } // a : d 次 // b : 2d + 1 次 long[] middle_product_(long[] a, long[] b, long mod, long gen) { int degree = a.length - 1; { int s = 0; int t = degree; while (s < t) { a[s] ^= a[t]; a[t] ^= a[s]; a[s] ^= a[t]; s++; t--; } } int level = Long.numberOfTrailingZeros(mod - 1); long root = gen; long omega = pow(root, (mod - 1) >> level, mod); int n = Integer.highestOneBit(2 * degree) << 1; long[] roots = new long[level]; long[] iroots = new long[level]; roots[0] = omega; iroots[0] = inv(omega, mod); for (int i = 1; i < level; ++i) { roots[i] = roots[i - 1] * roots[i - 1] % mod; iroots[i] = iroots[i - 1] * iroots[i - 1] % mod; } a = Arrays.copyOf(a, n); b = Arrays.copyOf(b, n); a = fft(a, true, mod, roots, iroots); b = fft(b, false, mod, roots, iroots); for (int i = 0; i < n; ++i) a[i] = a[i] * b[i] % mod; a = fft(a, true, mod, roots, iroots); long inv = inv(n, mod); for (int i = 0; i < n; ++i) { a[i] = a[i] * inv % mod; } return a; } long[] fft(long[] a, boolean inv, long mod, long[] roots, long[] iroots) { int n = a.length; int c = 0; for (int i = 1; i < n; ++i) { for (int j = n >> 1; j > (c ^= j); j >>= 1) ; if (c > i) { long d = a[i]; a[i] = a[c]; a[c] = d; } } int level = Long.numberOfTrailingZeros(mod - 1); for (int i = 1; i < n; i *= 2) { long w; if (!inv) w = roots[level - Integer.numberOfTrailingZeros(i) - 1]; else w = iroots[level - Integer.numberOfTrailingZeros(i) - 1]; for (int j = 0; j < n; j += 2 * i) { long wn = 1; for (int k = 0; k < i; ++k) { long u = a[j + k]; long v = a[j + k + i] * wn % mod; a[j + k] = u + v; a[j + k + i] = u - v; if (a[j + k] >= mod) a[j + k] -= mod; if (a[j + k + i] < 0) a[j + k + i] += mod; wn = wn * w % mod; } } } return a; } long pow(long a, long n, long mod) { long ret = 1; for (; n > 0; n >>= 1, a = a * a % mod) { if (n % 2 == 1) ret = ret * a % mod; } return ret; } long garner(long[] x, long[] mod, long mod0) { assert x.length == mod.length; int n = x.length; long[] gamma = new long[n]; for (int i = 0; i < n; i++) { long prod = 1; for (int j = 0; j < i; j++) { prod = prod * mod[j] % mod[i]; } gamma[i] = inv(prod, mod[i]); } long[] v = new long[n]; v[0] = x[0]; for (int i = 1; i < n; i++) { long tmp = v[i - 1]; for (int j = i - 2; j >= 0; j--) { tmp = (tmp * mod[j] + v[j]) % mod[i]; } v[i] = (x[i] - tmp) * gamma[i] % mod[i]; while (v[i] < 0) v[i] += mod[i]; } long ret = 0; for (int i = v.length - 1; i >= 0; i--) { ret = (ret * mod[i] + v[i]) % mod0; } return ret; } static void tr(Object... objects) { System.out.println(Arrays.deepToString(objects)); } }