RT，调好久了，最后三个点总是T

#include<bits/stdc++.h>
#define R register
using namespace std;
const long long MOD=10000007;
long long f[101][101];
long long a[201];
int cnt;
long long n;
long long power(int a, int b){
	long long ans=1LL,now=a;
	while(b){
		if(b&1) ans*=now,ans%=MOD;
        now*=now,now%=MOD;
		b>>=1;
	}
	return ans%MOD;
}
long long dfs(int pos,int now,int need,int limit){
	if(pos<1) return now==need;
	if(~f[pos][now]&&!limit) return f[pos][now];
	int maxn=limit?a[pos]:1;
	long long res=0;
	for(int i=0;i<=maxn;i++)res+=dfs(pos-1,now+(i==1),need,limit&&i==maxn);
	if (!limit)f[pos][now]=res;
	return res;
}
long long solve(long long x) {
	while(x) a[++cnt]=x&1,x>>=1;
	long long ans=1LL;
	for(int i=1;i<=cnt;i++) {
		memset(f,-1,sizeof(f));
		ans=ans*power(i,dfs(cnt,0,i,1))%MOD;
		ans%=MOD;
	}
	return ans;
}
int main() {
	cin >> n;
	cout << solve(n);
	return 0;
}