求乘积

const int N = 1e2 + 10,T = 20;

LL n;
LL a[N];
LL dp[N][N];//枚举的第i位,没有任何限制,已经填写了j个1的数的乘积
//表示在[pos + 1, len]中已经填写了cnt个1，[1, pos]任意填写数，所有合法方案的乘积

LL mo(LL x)
{
	return (x % mod + mod) % mod; 
}

LL dfs(int pos,bool lim,LL cnt)
{
	if (pos == 0) return max(cnt,1LL);//至少为1,数字1的二进制有1个1
	
	if (!lim && ~dp[pos][cnt]) return dp[pos][cnt];
	
	int up = lim?a[pos]:1;
	LL res = 1;
	for (int i = 0;i <= up;i ++)
	{
		res = mo(res * mo(dfs(pos - 1,lim && i == up,cnt + (i == 1))));
	} 
	
	if (!lim) dp[pos][cnt] = res;
	
	return res;
}

LL f(LL x)
{
	int len = 0;
	while(x)
	{
		a[ ++len] = x % 2;
		x /= 2;
	}
	return dfs(len,true,0);
	
}

void solve()
{
	cin >> n;
	cout << f(n) << endl;
}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _ = 1;
	// cin >> _;
	memset(dp,-1,sizeof dp);//可复用的，多组样例都可使用
	while(_--) solve();
	
	return 0;
}