#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair P; const int MAX=1000010; bitset isprime; void sieve(){ for(int i=3; i>n; sieve(); ll ans=1; bool ok=1; for(int p=n; p>=2; p--){ if(!isprime[p]) continue; ll q=p; while(q*p<=n){ q*=p; } if(ok && 2*q>n){ ok=0; ans*=(q/p); }else{ ans*=q; } ans%=MOD; } cout<