#include<iostream> #include<cstdio> #include<cmath> using namespace std; const int mod=1234567; int cal(long long &n) { long long tmp=1,s=2; while(tmp*2<=n-1) { tmp=tmp*2; s=s*s%mod; } n=n-tmp; return s; } int main() { long long n,i,s=1; cin>>n; if(n<=0) { cout<<"0"; return 0; } else if(n==1) { cout<<"1"; return 0; } while(n>1) s=s*cal(n)%mod; cout<<s; return 0; }