#include #include #include using namespace std; #define MOD 1000000007 map, long long int> mp; #define M 1000002 long long int F[M]; long long int ppow(long long int i, long long int j){ long long int res = 1; while (j){ if(j&1)res *= i; if (res >= MOD)res %= MOD; i *= i; i %= MOD; j >>= 1; } return res; } long long int inv[M]; long long int recfact(long long int start, long long int n) { long long int i; if (mp.count(make_pair(start, n) )){ return mp[make_pair(start, n)]; } if (start+n-1 <= M) { long long int r = inv[start]*F[start+n-1]; r %= MOD; //for (i = start + 1; i < start + n; i++) r *= i,r%=MOD; return r%MOD; } i = n / 2; mp[make_pair(start,n)]=(recfact(start, i) * recfact(start + i, n - i))%MOD; return mp[{start, n}]; } long long int factorial(long n) { return recfact(1, n); } int main(){ F[0] = 1; inv[0] = 1; for (int i = 1; i < M; i++){ F[i] = F[i - 1]; F[i] *= i; F[i] %= MOD; inv[i] = ppow(F[i], MOD - 1); } long long int n; scanf("%lld", &n); if (n >= MOD){ puts("0"); return 0; } long long int c = factorial(n); printf("%lld\n", c); return 0; }