#include<bits/stdc++.h>
#define int long long

using namespace std;
const int maxn=1e7+5e6;
const int mod=1e9+7;
int jc[maxn],inv[maxn],n;
int mp[maxn];
struct pair_hash
{
    bool operator() (const pair<int, int>& p) const
    {
        int h1 = (p.first);
        int h2 = mp[p.second];
        return h1 + h2 * maxn;
    }
};
unordered_map<pair<int, int>, int, pair_hash> dp;
int C(int n,int m){
	return jc[n]*inv[n-m]%mod*inv[m]%mod;
}
int ksm(int x,int p,int mod){
	int ans=1;
	while(p){
		if(p&1) ans=ans*x%mod;
		x=x*x%mod;
		p>>=1;
	}
	return ans;
}
int dfs(int x,int y){
	if(x==0) return 0;
	pair<int,int>t=make_pair(x,y);
	if(dp.find(t)!=dp.end()) return dp[t];
	int r=min(2*x,n-y);
	int z=min(2*y,n-y);
	int sum=n-y;
	int mn=max(0LL,r+z-sum);
	int mx=min(r,z);
	int ans=1;
	int fm=ksm(C(n-y,z),mod-2,mod);
	for(int i=mn;i<=mx;i++){
		ans+=C(r,i)*C(n-y-r,z-i)%mod*dfs(r-i,z+y)%mod*fm%mod;
		ans%=mod;
	}
	return dp[t]=ans;
}
void init(){
	jc[0]=inv[0]=1;
	for(int i=1;i<maxn;i++) jc[i]=i*jc[i-1]%mod;
	inv[maxn-1]=ksm(jc[maxn-1],mod-2,mod);
	for(int i=maxn-2;i>=1;i--){
		inv[i]=(i+1)*inv[i+1]%mod;
	}
	mp[1]=0;
	int base=3;
	for(int i=1;;i++){
		if(base>=n){
			mp[n]=i;
			break;
		}
		mp[base]=i;
		base*=3;
		
	}
}
signed main(){
	memset(dp,-1,sizeof(dp));
	init();
	int base=1;
	cin>>n;
	cout<<dfs(1,1)<<endl;
	return 0;
} 

answer.code: In function ‘int main()’:
answer.code:68:16: error: cannot convert ‘std::unordered_map<std::pair<long long int, long long int>, long long int, pair_hash>’ to ‘void*’
   68 |         memset(dp,-1,sizeof(dp));
      |                ^~
      |                |
      |                std::unordered_map<std::pair<long long int, long long int>, long long int, pair_hash>
In file included from /usr/include/features.h:461,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/os_defines.h:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/c++config.h:571,
                 from /usr/include/c++/11/cassert:43,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:33,
                 from answer.code:1:
/usr/include/x86_64-linux-gnu/bits/string_fortified.h:59:1: note:   initializing argument 1 of ‘void* memset(void*, int, size_t)’
   59 | __NTH (memset (void *__dest, int __ch, size_t __len))
      | ^~~~~