题解,求关注

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
typedef long long ll;
const int N=70,mod=10000007;
ll f[N][N];//表示后i位可以任选且前i位含有j个1的个数 
ll a[N];
ll qpow(ll a,ll b)
{
	ll ans=1;
	while(b)
	{
		if(b&1) ans=ans*a%mod;
		a=a%mod*a%mod;
		b>>=1;
	}
	return ans;
}
ll dp(int pos,int cnt,int limit,int t)//因为求的是指数，所以在求DP过程中不能模mod 
{
	if(!pos) return cnt==t;
	if(cnt>t) return 0;//剪枝 
	if(!limit&&f[pos][cnt]!=-1) return f[pos][cnt];
	ll ans=0;
	int up=limit?a[pos]:1;
	for(int i=0;i<=up;i++)
		ans+=dp(pos-1,cnt+(i==1),limit&&(i==up),t);
	if(!limit) f[pos][cnt]=ans;
	return ans;
}
ll solve(ll x)
{
	ll ans=1;
	int pos=0;
	while(x)
	{
		a[++pos]=x%2;
		x/=2;
	}
	for(int i=1;i<=pos;i++)
	{
		memset(f,-1,sizeof f);//因为我们每次求的满足条件不一样，所以每次都需要初始化 
		ans=ans*(qpow(i,dp(pos,0,1,i)))%mod;
	}
	return ans;
}
int main()
{
	ll n;
	cin>>n;
	cout<<solve(n);
	return 0;