//GIVE ME AC!!!!!!!!!!!!!!!!! //#pragma GCC target("avx") //#pragma GCC optimize("O3") //#pragma GCC optimize("unroll-loops") #include #define ll long long #define ld long double #define floatset() fixed<; using vi=vector; using vs=vector; using vc=vector; using vvl=vector; using P=pair; using vvc=vector; using vd=vector; using vp=vector

; using vb=vector; const int dx[8]={1,0,-1,0,1,-1,-1,1}; const int dy[8]={0,1,0,-1,1,1,-1,-1}; const ll inf=2e18; const ll MOD=1000000007; const ll mod=998244353; const double pi=acos(-1); template ostream &operator<<(ostream&os,const pair&p) { os< istream &operator>>(istream&is,pair&p) { is>>p.first>>p.second; return is; } template ostream &operator<<(ostream&os,const vector&v) { for(int i=0;i<(int)v.size();i++) { os< istream &operator>>(istream&is,vector&v) { for(T &in:v)is>>in; return is; } void scan(){} template void scan(Head&head,Tail&... tail) { cin>>head; scan(tail...); } template void print(const T &t) { cout << t << '\n'; } template void print(const Head &head, const Tail &... tail) { cout << head << ' '; print(tail...); } template void fin(const T &... a) { print(a...); exit(0); } template ll sum_(vector&v){ ll res=0; for(auto &e:v)res+=e; return res; } template inline bool chmax(T1&a,T2 b){return a inline bool chmin(T1&a,T2 b){return a>b&&(a=b,true);} #if __has_include() #include using mint = atcoder::modint1000000007; #endif template< class T > struct Matrix { vector>A; Matrix() {} Matrix(size_t n,size_t m):A(n,vector(m,0)){} Matrix(size_t n):A(n,vector(n,0)){}; size_t height(){ return (A.size()); } size_t width(){ return (A[0].size()); } inline const vector&operator[](int k)const{ return (A.at(k)); } inline vector&operator[](int k){ return (A.at(k)); } static Matrix E(size_t n){ Matrix mat(n); for(int i=0;i> C(n,vector(m,0)); for(int i=0;i0){ if(k&1)B*=*this; *this*=*this; k>>=1LL; } A.swap(B.A); return (*this); } Matrix operator+(Matrix&B){ return (Matrix(*this)+=B); } Matrix operator-(Matrix &B){ return (Matrix(*this)-=B); } Matrix operator*(Matrix&B){ return (Matrix(*this)*=B); } Matrix operator^(long long k){ return (Matrix(*this)^=k); } }; int main(){ LL(m,k); Matrixa(m); rep(n,0,m){ rep(i,0,m){ a[n][(n+i)%m]+=1; a[n][(n*i)%m]+=1; } } a^=k; fin(a[0][0].val()); }