题目背景

众所周知，花神多年来凭借无边的神力狂虐各大 OJ、OI、CF、TC …… 当然也包括 CH 啦。

题目描述

话说花神这天又来讲课了。课后照例有超级难的神题啦…… 我等蒟蒻又遭殃了。 花神的题目是这样的：设 sum(i)\text{sum}(i)sum(i) 表示 iii 的二进制表示中  的个数。给出一个正整数 NNN ，花神要问你 ∏i=1Nsum(i)\prod_{i=}^{N}\text{sum}(i)∏i=1N​sum(i) ，也就是 sum()∼sum(N)\text{sum}()\sim\text{sum}(N)sum()∼sum(N) 的乘积。

输入输出格式

输入格式：

一个正整数 N。

输出格式：

一个数，答案模  的值。

输入输出样例

输入样例#： 复制

输出样例#： 复制

说明

对于 % 的数据，N≤^

#include<iostream>

#include<cstdio>

#include<cmath>

#include<ctime>

#include<queue>

#include<algorithm>

#include<cstring>

using namespace std;

#define duke(i,a,n) for(register int i = a;i <= n;++i)

#define lv(i,a,n) for(register int i = a;i >= n;--i)

#define clean(a) memset(a,0,sizeof(a))

const int INF =  << ;

typedef long long ll;

typedef double db;

template <class T>

void read(T &x)

{

    char c;

    bool op = ;

    while(c = getchar(), c < '' || c > '')

        if(c == '-') op = ;

    x = c - '';

    while(c = getchar(), c >= '' && c <= '')

        x = x *  + c - '';

    if(op) x = -x;

}

template <class T>

void write(T x)

{

    if(x < ) putchar('-'), x = -x;

    if(x >= ) write(x / );

    putchar('' + x % );

}

const int N = ;

const int mod = ;

ll n;

int x[N],cnt = ;

ll f[N][][N][N];

ll ans[N];

ll qpow(ll a,ll b)

{

    ll tot = ;

    while(b)

    {

        if(b & )

        {

            tot *= a;

            tot %= mod;

        }

        a *= a;

        a %= mod;

        b >>= ;

    }

    return tot;

}

ll _f(int cur,int up,int tmp,int d)

{

    if(!cur)

    return tmp == d;

    if(~f[cur][up][tmp][d])

        return f[cur][up][tmp][d];

    int lim = up ? x[cur] : ;

    ll ret = ;

    for(int i = ;i <= lim;++i)

    {

        ret += _f(cur - ,up && i == lim,tmp + (i == ),d);

    }

    return f[cur][up][tmp][d] = ret;

}

ll solve()

{

    while(n)

    {

        x[++cnt] = n & ;

        n >>= ;

    }

    for(int i = ;i <= ;i++)

    {

        memset(f,-,sizeof(f));

        ans[i] = _f(cnt,,,i);

    }

    ll ret = ;

    for(int i = ;i <= ;++i)

    {

        ret = ret * qpow(i,ans[i]) % mod;

    }

}

int main()

{

    read(n);

    printf("%lld\n",solve());

}