#pragma GCC target("avx2") #pragma GCC optimize("Ofast") #include #include #include #include namespace mp__=boost::multiprecision; using bint=mp__::cpp_int; using greatd=mp__::number>; using namespace std; template using V=vector; template using VV=V>; using ll=long long; using ull=unsigned long long; using ld=long double; using pii=pair; using pll=pair; using pli=pair; using pil=pair; using pdd=pair; using vi=vector; using vvi=V; using vpi=vector; using vvpi=V; using vl=vector; using vvl=V; using vs=vector; using vvs=V; using vc=vector; using vvc=V; using vd=vector; using vvd=V; using vpl=vector; using vvpl=V; using vpil=vector>; using vvpil=V; using vpli=vector>; using vvpli=V; using vpd=vector; using vvpd=V; using vb=vector; using vvb=V; template using pq=priority_queue,greater>; template using rpq=priority_queue>; templateostream &operator<<(ostream &os,const pair &p){os <istream &operator>>(istream &is,pair &p){is >>p.first >>p.second;return is;} #define ovl4(a,b,c,d,name,...) name #define rep1(n) for(int i=0; i=0; i--) #define rrep2(i,a) for(int i=a; i>=0; i--) #define rrep3(i,a,b) for(int i=a; i>=b; i--) #define rrep4(i,a,b,c) for(int i=a; i>=b; i-=c) #define rrep(...) ovl4(__VA_ARGS__,rrep4,rrep3,rrep2,rrep1)(__VA_ARGS__) #define atrep(i,v) for(auto i:v) void in(){} templatevoid in(T&... a){(cin >>... >>a);} template void vin(vector &v,int n=-1,int s=0){if(n==-1)n=v.size();rep(i,s,s+n)in(v[i]);} #define INT(...) int __VA_ARGS__;in(__VA_ARGS__) #define LL(...) ll __VA_ARGS__;in(__VA_ARGS__) #define ULL(...) ull __VA_ARGS__;in(__VA_ARGS__) #define DBL(...) double __VA_ARGS__;in(__VA_ARGS__) #define LD(...) ld __VA_ARGS__;in(__VA_ARGS__) #define STR(...) string __VA_ARGS__;in(__VA_ARGS__) #define CHR(...) char __VA_ARGS__;in(__VA_ARGS__) void VIN(){} template void VIN(int ind,vector& v,Ts&... vs){vin(v,v.size()-ind,ind);if constexpr(sizeof...(vs)>0)VIN(ind,vs...);} template bool chmax(T &a,Ts... b){T c=a;for(auto i:{b...})a=max(a,i);return a==c;} template bool chmin(T &a,Ts... b){T c=a;for(auto i:{b...})a=min(a,i);return a==c;} template bool chcomp(function comp,T &a,Ts... b){T c=a;for(auto i:{b...})a=comp(a,i);return a==c;} void print(){cout<<"\n";} template void print(const T &a,const Ts&... b){cout < void vprint(vector &v,bool ind1=false,string aid=" "){rep(i,(int)ind1,v.size()){if(i>(int)ind1){cout < bool eql(const T &a){return true;}; template bool eql(const T& a,const Ts&... b){bool ret=true;for(auto i:{b...})ret&=(i==a);return ret;} bool operator==(const string& a,const string& b){return a.compare(b)==0;} random_device rd; mt19937 mt(rd()); const int INF=1e9; const ll LINF=1e18; const ll MOD=1e9+7; const ll MMOD=998244353; const ld eps=1e-10; const ld PI=M_PI; bool deql(const ld &a){return true;} template bool deql(const ld& a,const Args&... b){bool ret=true;for(auto i:{b...})ret&=(inr(-eps,i-a,eps));return ret;} int dx[8]={-1,0,1,0,-1,-1,1,1},dy[8]={0,1,0,-1,-1,1,1,-1}; class xorshift{ private:uint64_t x; public: xorshift(){mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());x=rnd();for(int i=0; i<100; i++)random();} uint64_t random(){x=x^(x<<7);return x=x^(x>>9);} };xorshift rnd; vector> matpow(vector> &mat,int n,long long m=1e18){ int len=mat.size(); vector> ret(len,vector(len)),a=mat; for(int i=0; i0){ if(n&1){ vector> p(len,vector(len)); for(int i=0; i> p(len,vector(len)); for(int i=0; i>=1; } return ret; } int main(){ ios::sync_with_stdio(false);std::cin.tie(nullptr);cout.tie(nullptr);FIX; INT(n); LL(m); vvl f(2,vl(2,1)); f[1][1]=0; f=matpow(f,n-2,m); print(f[0][0]); return 0; }