#include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; const ll INF=1LL<<60; typedef pair P; typedef pair PP; const ll MOD=1e9+7; vector > mat(vector > A,vector > B,int N){ //A*B vector > C(N,vector(N)); for(int i=0;i> multi_matrix(vector> x, ll y ,int N){ vector > pow(N,vector(N)); for(int i=0;i0){ if(y&1){ pow = mat(pow,x,N); } y = y>>1; x = mat(x,x,N); } return pow; } int main(){ ll N; cin>>N; if(N%2==1){ //最大マッチングが0の1とおり cout<<1<> A(2,vector(2,0)); A[0][0]=1,A[0][1]=1; A[1][0]=1,A[1][1]=0; ll n=N/2; if(N==2){ cout<<1<