#include <iostream>
using namespace std;
unsigned int x[90],y[90];
int main()
{
int n;
int i,j,k;
unsigned long long s=1;
cin>>n;
n--;
x[0]=2;
y[0]=1;
for(i=0,j=0;i<n;)
{
for(k=j;k>=0;k--)
if (y[k]+i<=n)
{
i+=y[k];
s*=x[k];
s%=1234567;
x[++j] = s;
y[j] = i;
break;
}
}
cout<<s<<endl;
return 0;
}

嘟嘟死理性（C++）