#include #include #include #include using namespace std; typedef long long LL; LL zero=false; LL one = true; LL MOD; LL getMod(); LL add(LL a,LL b){ while(b!=zero){ LL c = (a&b)< keta; while(B){ if(B&one){ keta.push_back(one); }else{ keta.push_back(zero); } B >>= one; } reverse(keta.begin(),keta.end()); int size = keta.size(); for(int i=zero;i V; LL ama(LL A){ int size = V.size(); for(int i=zero;i= V[i]){ A -= V[i]; } } return A; } vector< vector > MUL( vector >& A,vector< vector >& B){ LL mod = MOD; int R = A.size(); int cen = A[zero].size(); int C = B[zero].size(); vector< vector > ans(R,vector(C,zero) ); for(int row=zero;row > powMod(const vector< vector >& mat,LL N,LL mod=MOD){ int R = mat.size(); int C = mat[zero].size(); vector< vector > I(R,vector(C,zero)); for(int i=zero;i > mul(R,vector(C)),ans(R,vector(C)); ans = I; mul = mat; while(N){ if( N & one ){ ans = MUL(ans,mul); } N >>= one; mul = MUL(mul,mul); } return ans; } signed main() { MOD = getMod(); { LL temp = MOD; while(temp>=zero){ V.push_back( temp ); temp <<= one; } reverse(V.begin(),V.end() ); } int T; cin>>T; vector< vector > R(one<(one< > A(one<(one)); A[zero][zero] = one; A[one][zero] = one<>N; if( N== one){ cout << one << endl; continue; } vector > res = powMod(R,N); vector > ans = MUL(res,A); cout << ans[one][zero] << endl; } } LL getMod(){ long long MOD = zero; MOD<<=one;MOD|=one; MOD<<=one;MOD|=one; MOD<<=one;MOD|=one; MOD<<=one; MOD<<=one;MOD|=one; MOD<<=one;MOD|=one; MOD<<=one;MOD|=one; MOD<<=one; MOD<<=one; MOD<<=one;MOD|=one; MOD<<=one;MOD|=one; MOD<<=one; MOD<<=one;MOD|=one; MOD<<=one; MOD<<=one;MOD|=one; MOD<<=one;MOD|=one; MOD<<=one; MOD<<=one; MOD<<=one;MOD|=one; MOD<<=one; MOD<<=one;MOD|=one; MOD<<=one; MOD<<=one; MOD<<=one; MOD<<=one; MOD<<=one; MOD<<=one; MOD<<=one;MOD|=one; MOD<<=one;MOD|=one; MOD<<=one;MOD|=one; return MOD; }