披着数论题外衣的数位dp。

相当于数一数$[1,n]$范围内$1$的个数是$1,2,3,4,...log(n)$的数各有多少个，直接在二进制下数位dp。

然而我比较sb地把(1e7 + 7)当成了质数，其实数出来的数是要模$\phi(p)$的，然而数出来的数绝对不会超过$n$。

时间复杂度$O(log^{4}n + \sqrt{P})$。

Code：

#include 
      
       #include 
       
        using namespace std;typedef long long ll;const int N = 65;const ll P = 1e7 + 7;int len, bit[N];ll f[N][N], phiP;inline ll pow(ll x, ll y) {    ll res = 1LL;    for(; y > 0; y >>= 1) {        if(y & 1) res = res * x % P;        x = x * x % P;    }     return res;}ll dfs(int pos, int cnt, bool lead, bool lim, int cur) {    if(pos == 0) return (cnt == cur);    if(!lead && !lim && f[pos][cnt] != -1) return f[pos][cnt];        ll res = 0LL; int num = lim ? bit[pos] : 1;    for(int i = 0; i <= num; i++)        res = (res + dfs(pos - 1, cnt + (i == 1), lead && (i == 0), lim && (i == bit[pos]), cur)) % phiP;        if(!lim && !lead) f[pos][cnt] = res;    return res;}inline ll solve(int k) {    memset(f, -1, sizeof(f));    ll res = dfs(len, 0, 1, 1, k);    return res;}inline ll getPhi(ll now) {    ll res = now, tmp = now;     for(int i = 2; i * i <= now; i++)         if(tmp % i == 0) {            res = res / i * (i - 1);            for(; tmp % i == 0; tmp /= i);        }    if(tmp != 1) res = res / tmp * (tmp - 1);    return res;}int main() {    phiP = getPhi(P);//    printf("%lld\n", phiP);        ll n; scanf("%lld", &n);        len = 0;    for(ll tmp = n; tmp > 0; tmp >>= 1)        bit[++len] = (tmp & 1);        ll ans = 1LL;    for(int i = 1; i <= len; i++)        ans = ans * pow(i, solve(i) % phiP) % P;        printf("%lld\n", ans);    return 0;}