Description

【题意】
 $a_n$ 表示 $n$ 转成 2 进制中1的个数，求 $(a_1*a_3*......*a_{n-2}*a_n)\bmod (10^8+7)$。

【输入格式】
一行一个数$n$($1 \le n \le 10^{15}$)，并保证$n$为奇数。

【输出格式】
输出一行一个整数。

【样例输入】
3

【样例输出】
2

Hint

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL mod=1e8+7;
LL qpow(LL a,LL b)
{
    LL res=1; 
    for(a%=mod;b;b>>=1,a=a*a%mod)if(b&1)res=res*a%mod;
    return res;
}
LL f[70][70],c[70],d[70];
//f[i][j]表示i位含j个1的方案数 
//c[i]表示有i个1的数有多少个 
int main()
{
	int D=log2(1e15)+1;
    d[0]=1;for(int i=1;i<=D;i++)d[i]=d[i-1]*2;
    for(int i=0;i<=D;i++)f[i][0]=1;
    for(int i=1;i<=D;i++)for(int j=1;j<=i;j++)f[i][j]=f[i-1][j-1]+f[i-1][j];
    LL n,t=0;scanf("%lld",&n);
    n=(n+1)/2;
    for(int i=D;i>=0;i--)
    {
        if(n>=d[i])
        {
            n-=d[i];
            t++;
            for(int j=0;j<=i;j++)c[t+j]+=f[i][j];
        }
    }
    LL ans=1;
    for(int i=1;c[i];i++)ans=ans*qpow(i,c[i])%mod;
    printf("%lld\n",ans);
    return 0;
}