#include<bits/stdc++.h> #include<atcoder/all> using namespace std; using namespace atcoder; typedef modint1000000007 mint; typedef long long ll; mint Garner(vector<long long> m,vector<long long> r){ int n = m.size(); vector<long long> t(n); for(int i=0; i<n; i++){ long long cur = 0LL; long long cm = 1LL; for(int j=0; j<i; j++){ cur += t[j] * cm; cur %= m[i]; cm *= m[j]; cm %= m[i]; } cur = r[i] - cur; cur %= m[i]; if(cur<0)cur += m[i]; if(i==1)cur *= 416537774; if(i==2)cur *= 429847628; //cur *= inv_mod(cm,m[i]); cur %= m[i]; t[i] = cur; } mint ret = 0; mint cm = 1; for(int i=0; i<n; i++){ ret += cm * t[i]; cm *= m[i]; } return ret; } template <class T> vector<T> convolution_mint(vector<T> a,vector<T> b){ static constexpr unsigned long long M0 = 998244353; static constexpr unsigned long long M1 = 754974721; static constexpr unsigned long long M2 = 469762049; vector<long long> aa(a.size()),bb(b.size()); for(int i=0; i<a.size(); i++)aa[i] = a[i].val(); for(int i=0; i<b.size(); i++)bb[i] = b[i].val(); auto c0 = convolution<M0>(aa,bb); auto c1 = convolution<M1>(aa,bb); auto c2 = convolution<M2>(aa,bb); vector<mint> ret(c0.size()); vector<long long> m = {M0,M1,M2}; for(int i=0; i<c0.size(); i++){ vector<long long> r = {c0[i],c1[i],c2[i]}; vector<long long> t(3); for(int j=0; j<3; j++){ long long cur = 0LL; long long cm = 1LL; for(int k=0; k<j; k++){ cur += t[k] * cm; cur %= m[j]; cm *= m[k]; cm %= m[j]; } cur = r[j] - cur; cur %= m[j]; if(cur<0)cur += m[j]; if(j==1)cur *= 416537774; if(j==2)cur *= 429847628; cur %= m[j]; t[j] = cur; } mint cm = 1; for(int j=0; j<3; j++){ ret[i] += cm * t[j]; cm *= m[j]; } } return ret; } vector<mint> poly_inv(vector<mint> &a, int M = -314159265){ if (M == -314159265) M = (int)a.size(); else if (M <= 0) return {}; int n = a.size(); mint r = a[0].pow(mint::mod()-2); int m = 1; vector<mint> res = {r}; while (m < M){ vector<mint> f = a; f.resize(min(n, 2*m)); vector<mint> h = convolution_mint(f, res); for (int i=0; i<min(2*m, (int)h.size()); i++){ h[i] = -h[i]; } h[0] += 2; h.resize(2*m); h = convolution_mint(h, res); h.resize(2*m); swap(res, h); m <<= 1; } res.resize(M); return res; } int ceil_pow2(int n) { int x = 0; while ((1U << x) < (unsigned int)(n)) x++; return x; } vector<mint> multi_eval(vector<mint> x, vector<mint> a){ int n = x.size(); int siz = 1 << ceil_pow2(n); vector<vector<mint>> g(2*siz, vector<mint>{1}); for (int i=0; i<n; i++) g[i + siz] = {-x[i], 1}; for (int i=siz-1; i>0; i--) g[i] = convolution_mint(g[2*i], g[2*i+1]); vector<mint> f; for (int i=1; i<2*siz; i++){ if (i==1) f = a; else f = g[i>>1]; int fs = f.size(), gs = g[i].size(); int m = fs - gs + 1; vector<mint> v = {}, w = {}; if (m > 0){ vector<mint> ft(m); for (int j=0; j<m; j++) ft[j] = f[fs-1-j]; vector<mint> gt(gs); for (int j=0; j<gs; j++) gt[j] = g[i][gs-1-j]; v = convolution_mint(ft, poly_inv(gt, m)); v.resize(m); reverse(v.begin(), v.end()); w = convolution_mint(v, g[i]); } g[i] = f; for (int j=0; j<w.size(); j++){ g[i][j] -= w[j]; } while (g[i].size() > 1 && g[i][g[i].size() - 1] == 0){ g[i].pop_back(); } } vector<mint> ret(n); for (int i=0; i<n; i++){ ret[i] = g[i+siz][0]; } return ret; } int main(){ ll n; cin >> n; if (n >= mint::mod()){ cout << 0 << endl; return 0; } clock_t start = clock(); int m = 61200; deque<vector<mint>> que; for (int i=0; i<m; i++){ que.push_back({i+1, 1}); } while(que.size() > 1){ vector<mint> f = que.front(); que.pop_front(); vector<mint> g = que.front(); que.pop_front(); que.push_back(convolution_mint(f, g)); } vector<mint> f = que.front(); vector<mint> g(n/m); for (int i=0; i<n/m; i++){ g[i] = i*m; } vector<mint> muleval = multi_eval(g, f); mint ans = 1; for (int i=m*(n/m)+1; i<=n; i++){ ans *= i; } for (int i=0; i<n/m; i++){ ans *= muleval[i]; } cout << ans.val() << endl; clock_t end = clock(); // η΅δΊζι //std::cout << "duration = " << (double)(end - start) / CLOCKS_PER_SEC << "sec.\n"; }