//Utkarsh.25dec #include <bits/stdc++.h> #define ll long long int #define pb push_back #define mp make_pair #define mod 1000000007 #define vl vector <ll> #define all(c) (c).begin(),(c).end() using namespace std; ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} ll modInverse(ll a){return power(a,mod-2);} const int N=500023; bool vis[N]; vector <int> adj[N]; long long readInt(long long l,long long r,char endd){ long long x=0; int cnt=0; int fi=-1; bool is_neg=false; while(true){ char g=getchar(); if(g=='-'){ assert(fi==-1); is_neg=true; continue; } if('0'<=g && g<='9'){ x*=10; x+=g-'0'; if(cnt==0){ fi=g-'0'; } cnt++; assert(fi!=0 || cnt==1); assert(fi!=0 || is_neg==false); assert(!(cnt>19 || ( cnt==19 && fi>1) )); } else if(g==endd){ if(is_neg){ x= -x; } if(!(l <= x && x <= r)) { cerr << l << ' ' << r << ' ' << x << '\n'; assert(1 == 0); } return x; } else { assert(false); } } } string readString(int l,int r,char endd){ string ret=""; int cnt=0; while(true){ char g=getchar(); assert(g!=-1); if(g==endd){ break; } cnt++; ret+=g; } assert(l<=cnt && cnt<=r); return ret; } long long readIntSp(long long l,long long r){ return readInt(l,r,' '); } long long readIntLn(long long l,long long r){ return readInt(l,r,'\n'); } string readStringLn(int l,int r){ return readString(l,r,'\n'); } string readStringSp(int l,int r){ return readString(l,r,' '); } int isgood[(1<<20)+1]={0}; int badnumbers[(1<<20)+1]={0}; void solve() { int n=readInt(1,60,'\n'); isgood[0]=1; for(int i=1;i<(1<<20);i++) { int j; for(j=19;j>=0;j--) { if((i&(1<<j))!=0) break; } int ele=j+1; int msk=(i^(1<<j)); if(isgood[msk]==0) { isgood[i]=0; continue; } isgood[i]=1; badnumbers[i]=badnumbers[msk]; for(int j=0;j<20;j++) { if((msk&(1<<j))!=0) { if((ele%(j+1))==0) badnumbers[i]|=(1<<(ele-1)); } } int badmsk=badnumbers[msk]; for(int j=0;j<20;j++) { if((badmsk&(1<<j))!=0) { if((ele%(j+1))==0) { isgood[i]=0; break; } } } } if(n<=20) { ll ans=0; for(int i=0;i<(1<<n);i++) ans+=isgood[i]; cout<<ans<<'\n'; } else { ll ans=0; for(int i=0;i<(1<<20);i++) { if(isgood[i]==0) continue; int mark[n+1]={0}; int ele=n-20; for(int j=0;j<20;j++) { if((badnumbers[i]&(1<<j))!=0) { for(int k=2*(j+1);k<=n;k+=(j+1)) { if(k<=20) continue; if(mark[k]==1) continue; mark[k]=1; ele--; } } } vector <pair<int,int>> v; for(int x=21;x<=n;x++) { if(2*x>n) break; if(mark[x]==1 || mark[2*x]==1) continue; for(int y=1;y<=20;y++) { if(x%y==0 && (i&(1<<(y-1)))!=0) { ele-=2; v.pb(mp(x,2*x)); break; } } } ans+=(1LL<<ele)*power(3,v.size()); } cout<<ans<<'\n'; } } int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif ios_base::sync_with_stdio(false); cin.tie(NULL),cout.tie(NULL); int T=1; //cin>>T; while(T--) solve(); cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n"; }