#include using namespace std; #define LOCAL #pragma region Macros typedef long long ll; #define ALL(x) (x).begin(),(x).end() const long long MOD=1000000007; // const long long MOD=998244353; const int INF=1e9; const long long IINF=1e18; const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1}; const char dir[4]={'D','R','U','L'}; template istream &operator>>(istream &is,vector &v){ for (T &x:v) is >> x; return is; } template ostream &operator<<(ostream &os,const vector &v){ for (int i=0;i ostream &operator<<(ostream &os,const pair &p){ os << '(' << p.first << ',' << p.second << ')'; return os; } template ostream &operator<<(ostream &os,const map &m){ os << '{'; for (auto itr=m.begin();itr!=m.end();++itr){ os << '(' << itr->first << ',' << itr->second << ')'; if (++itr!=m.end()) os << ','; --itr; } os << '}'; return os; } template ostream &operator<<(ostream &os,const set &s){ os << '{'; for (auto itr=s.begin();itr!=s.end();++itr){ os << *itr; if (++itr!=s.end()) os << ','; --itr; } os << '}'; return os; } void debug_out(){cerr << '\n';} template void debug_out(Head&& head,Tail&&... tail){ cerr << head; if (sizeof...(Tail)>0) cerr << ", "; debug_out(move(tail)...); } #ifdef LOCAL #define debug(...) cerr << " ";\ cerr << #__VA_ARGS__ << " :[" << __LINE__ << ":" << __FUNCTION__ << "]" << '\n';\ cerr << " ";\ debug_out(__VA_ARGS__) #else #define debug(...) 42 #endif template T gcd(T x,T y){return y!=0?gcd(y,x%y):x;} template T lcm(T x,T y){return x/gcd(x,y)*y;} template inline bool chmin(T1 &a,T2 b){ if (a>b){a=b; return true;} return false; } template inline bool chmax(T1 &a,T2 b){ if (a=get_mod()) a-=get_mod(); return *this; } runtime_modint operator+(const runtime_modint &rhs) const{ return runtime_modint(*this)+=rhs; } runtime_modint &operator-=(const runtime_modint &rhs){ if (a>=1; } return *this; } runtime_modint operator/(const runtime_modint &rhs) const{ return runtime_modint(*this)/=rhs; } friend runtime_modint pow(runtime_modint rhs,long long exp) noexcept{ runtime_modint res{1}; while(exp){ if (exp&1) res*=rhs; rhs*=rhs; exp>>=1; } return res; } friend ostream &operator<<(ostream &s,const runtime_modint &rhs){ return s << rhs.a; } friend istream &operator>>(istream &s,runtime_modint &rhs){ u64 a; rhs=runtime_modint{(s >> a,a)}; return s; } }; template struct Matrix{ vector> dat; Matrix(size_t r,size_t c):dat(r,vector(c,K())){} Matrix(size_t n):dat(n,vector(n,K())){} Matrix(vector> dat):dat(dat){} size_t size() const{return dat.size();} vector &operator[](int i){return dat[i];} const vector &operator[](int i) const{return dat[i];} static Matrix I(size_t n){ Matrix res(n); for (int i=0;i> res(dat.size(),vector(B[0].size(),K())); for (int i=0;i>=1LL; } dat.swap(res.dat); return (*this); } Matrix operator^(long long k) const{ return Matrix(*this)^=k; } static Matrix Gauss_Jordan(const Matrix &A,const Matrix &B){ int n=A.size(),l=B[0].size(); Matrix C(n,n+l); for (int i=0;i> N >> M; mint::set_mod(M); Matrix m(2); m[0][1]=m[1][0]=m[1][1]=1; m^=N; cout << m[0][0] << '\n'; }