#include #include #include using namespace std; class UnionFind { public: explicit UnionFind(int N) : root(N, -1), size(N, 1) {} int getRoot(int u){ return root[u] == -1 ? u : root[u] = getRoot(root[u]); } int getSize(int u){ return size[getRoot(u)]; } bool same(int a, int b){ return getRoot(a) == getRoot(b); } bool merge(int a, int b){ int u = getRoot(a); int v = getRoot(b); if(u == v) return false; root[u] = v; size[v] += size[u]; return true; } private: vector root; vector size; }; int naive(int N){ vector> vp; for(int i=0;i cnt(vp.size()+1, 0); for(int i=0;i<(1< 10) return 0; long long v = 0; for(auto& c : s) v = 10 * v + c - '0'; if(v > MOD) return 0; --v; long long res = fact[v/1000000]; long long base = v/1000000*1000000; for(int i=base+1;i<=v;i++){ res = res * i % MOD; } return (v%2 == 0 ? res : (MOD-res)%MOD); } int main(){ // long long m = 1; // cout << "long long fact[] = {" << endl << " 1, "; // for(int i=2;i> s; cout << solve(s) << endl; }