#include using namespace std; //入力が必ず-mod<=a //mod<2^30. struct modint{ //mod変更が不可能. public: long long v; static void setmod(int m){} //飾り. static constexpr long long getmod(){return mod;} modint():v(0){} template modint(T a):v(a){if(v < 0) v += mod;} long long val()const{return v;} modint &operator=(const modint &b) = default; modint &operator+()const{return (*this);} modint operator-()const{return modint(0)-(*this);} modint operator+(const modint b)const{return modint(v)+=b;} modint operator-(const modint b)const{return modint(v)-=b;} modint operator*(const modint b)const{return modint(v)*=b;} modint operator/(const modint b)const{return modint(v)/=b;} modint &operator+=(const modint b){ v += b.v; if(v >= mod) v -= mod; return *this; } modint &operator-=(const modint b){ v -= b.v; if(v < 0) v += mod; return *this; } modint &operator*=(const modint b){v = v*b.v%mod; return *this;} modint &operator/=(modint b){ //b!=0 mod素数が必須. assert(b.v != 0); (*this) *= b.pow(mod-2); return *this; } modint pow(long long n)const{ modint ret = 1,p = v; if(n < 0) p = p.inv(),n = -n; while(n){ if(n&1) ret *= p; p *= p; n >>= 1; } return ret; } modint inv()const{return pow(mod-2);} //素数mod必須. modint &operator++(){*this += 1; return *this;} modint &operator--(){*this -= 1; return *this;} modint operator++(int){modint ret = *this; *this += 1; return ret;} modint operator--(int){modint ret = *this; *this -= 1; return ret;} friend bool operator==(const modint a,const modint b){return a.v==b.v;} friend bool operator!=(const modint a,const modint b){return a.v!=b.v;} friend bool operator<(const modint a,const modint b){return a.v=(const modint a,const modint b){return a.v>=b.v;} friend bool operator>(const modint a,const modint b){return a.v>b.v;} friend ostream &operator<<(ostream &os,const modint a){return os<>(istream &is,modint &a){ //入力はmodをとってくれる. long long x; is >> x; x %= mod; a = modint(x); return is; } }; //入力が必ず-mod //modが入力で与えられる場合. struct dynamic_modint{ //mod変更が可能 最初にsetmod必須 idxで複数個所持が可能. private: static int mod; public: long long v; static constexpr long long getmod(){return mod;} static void setmod(int m){ assert(m > 0); mod = m; } dynamic_modint():v(0){} template dynamic_modint(T a):v(a){if(v < 0) v += mod;} long long val()const{return v;} dynamic_modint &operator=(const dynamic_modint &b) = default; dynamic_modint &operator+()const{return (*this);} dynamic_modint operator-()const{return dynamic_modint(0)-(*this);} dynamic_modint operator+(const dynamic_modint b)const{return dynamic_modint(v)+=b;} dynamic_modint operator-(const dynamic_modint b)const{return dynamic_modint(v)-=b;} dynamic_modint operator*(const dynamic_modint b)const{return dynamic_modint(v)*=b;} dynamic_modint operator/(const dynamic_modint b)const{return dynamic_modint(v)/=b;} dynamic_modint &operator+=(const dynamic_modint b){ v += b.v; if(v >= mod) v -= mod; return *this; } dynamic_modint &operator-=(const dynamic_modint b){ v -= b.v; if(v < 0) v += mod; return *this; } dynamic_modint &operator*=(const dynamic_modint b){v = v*b.v%mod; return *this;} dynamic_modint &operator/=(dynamic_modint b){ //b!=0 mod素数が必須. assert(b.v != 0); (*this) *= b.pow(mod-2); return *this; } dynamic_modint pow(long long n)const{ dynamic_modint ret = 1,p = v; if(n < 0) p = p.inv(),n = -n; while(n){if(n&1) ret *= p; p *= p,n >>= 1;} return ret; } dynamic_modint inv()const{return pow(mod-2);} //素数mod必須. dynamic_modint &operator++(){*this += 1; return *this;} dynamic_modint &operator--(){*this -= 1; return *this;} dynamic_modint operator++(int){dynamic_modint ret = *this; *this += 1; return ret;} dynamic_modint operator--(int){dynamic_modint ret = *this; *this -= 1; return ret;} friend bool operator==(const dynamic_modint a,const dynamic_modint b){return a.v==b.v;} friend bool operator!=(const dynamic_modint a,const dynamic_modint b){return a.v!=b.v;} friend bool operator<(const dynamic_modint a,const dynamic_modint b){return a.v=(const dynamic_modint a,const dynamic_modint b){return a.v>=b.v;} friend bool operator>(const dynamic_modint a,const dynamic_modint b){return a.v>b.v;} friend ostream &operator<<(ostream &os,const dynamic_modint a){return os<>(istream &is,dynamic_modint &a){ //入力はmodをとってくれる. long long x; is >> x; x %= mod; a = dynamic_modint(x); return is; } }; template int dynamic_modint::mod=998244353; using mint = dynamic_modint<0>; namespace to_fold{ __int128_t safemod(__int128_t a,long long m){a %= m; if(a < 0) a += m; return a;} pair invgcd(long long a,long long b){ //return {gcd(a,b),x} (xa≡g(mod b)) a = safemod(a,b); if(a == 0) return {b,0}; long long x = 0,y = 1,memob = b; while(a){ long long q = b/a; b -= a*q; swap(x,y); y -= q*x; swap(a,b); } if(x < 0) x += memob/b; return {b,x}; } long long mod; long long Garner(const vector &A,const vector &M){ __int128_t mulM = 1,x = A.at(0)%M.at(0); //Mの要素のペア互いに素必須. for(int i=1; i struct fftinfo{ static bool First; static mint g,sum_e[30],sum_ie[30]; //sum_e[i]=Π[j=0~i-1]ies[j] * es[i],sum_ie[i]=Π[i=0~j-1]es[j] * ies[i]. static mint divpow2[30]; //div[i] = 1/(2^i). static mint Zeta[30]; fftinfo(){ if(!First) return; First = false; const long long mod = mint::getmod(); if(mod == 998244353) g = 3; else if(mod == 754974721) g = 11; else if(mod == 167772161) g = 3; else if(mod == 469762049) g = 3; else assert(false); //現状RE. mint es[30],ies[30]; //es[i]^(2^(2+i))=1. int cnt2 = countzero(mod-1); mint e = g.pow((mod-1)>>cnt2),ie = e.inv(); for(int i=cnt2; i>=2; i--){ //e^(2^i)=1; es[i-2] = e,e *= e; ies[i-2] = ie,ie *= ie; } mint rot = 1; for(int i=0; i<=cnt2-2; i++) sum_e[i] = es[i]*rot,rot *= ies[i]; rot = 1; for(int i=0; i<=cnt2-2; i++) sum_ie[i] = ies[i]*rot,rot *= es[i]; mint div2n = 1,div2 = mint(1)/2; for(int i=0; i<30; i++) divpow2[i] = div2n,div2n *= div2; for(int i=0; i<=cnt2; i++) Zeta[i] = g.pow((mod-1)/(2< bool fftinfo::First=true; template mint fftinfo::g; template mint fftinfo::sum_e[30]; template mint fftinfo::sum_ie[30]; template mint fftinfo::divpow2[30]; template mint fftinfo::Zeta[30]; template void NTT(vector &A){ //ACLを超参考にしてる. int n = A.size(); assert((n&-n) == n); fftinfo info; int h = countzero(n); for(int ph=1; ph<=h; ph++){ int w = 1<<(ph-1),p = 1<<(h-ph); mint rot = 1; for(int s=0; s void INTT(vector &A){ int n = A.size(); assert((n&-n) == n); fftinfo info; const unsigned int mod = mint::getmod(); int h = countzero(n); for(int ph=h; ph>0; ph--){ int w = 1<<(ph-1),p = 1<<(h-ph); mint irot = 1; for(int s=0; s vector convolution(vector A,vector B){ //mintじゃないのを突っ込まないように!!!. int siza = A.size(),sizb = B.size(),sizc = siza+sizb-1,N = 1; if(siza == 0 || sizb == 0) return {}; if(min(siza,sizb) <= 60){ //naive. vector ret(sizc); if(siza >= sizb){for(int i=0; i vector convolution_ll(const vector &A,const vector &B){ //long longに収まる範囲. int siza = A.size(),sizb = B.size(),sizc = siza+sizb-1; if(siza == 0 || sizb == 0) return {}; vector ret(sizc); if(min(siza,sizb) <= 200){ //naive 200はやばい?. if(siza >= sizb){for(int i=0; i; using mint2 = modint; using mint3 = modint; vector a1(siza),b1(sizb); vector a2(siza),b2(sizb); vector a3(siza),b3(sizb); for(int i=0; i C1 = convolution(a1,b1); for(int i=0; i C2 = convolution(a2,b2); for(int i=0; i C3 = convolution(a3,b3); vector offset = {0,0,m1m2m3,2*m1m2m3,3*m1m2m3}; for(int i=0; i vector convolution_llmod(const vector &A,const vector &B){ int siza = A.size(),sizb = B.size(),sizc = siza+sizb-1; if(siza == 0 || sizb == 0) return {}; vector ret(sizc); if(min(siza,sizb) <= 200){ for(int i=0; i; using mint2 = modint; using mint3 = modint; vector a1(siza),b1(sizb); vector a2(siza),b2(sizb); vector a3(siza),b3(sizb); for(int i=0; i C1 = convolution(a1,b1); for(int i=0; i C2 = convolution(a2,b2); for(int i=0; i C3 = convolution(a3,b3); for(int i=0; i A = {C1.at(i).v,C2.at(i).v,C3.at(i).v}; vector M = {mod1,mod2,mod3}; ret.at(i) = Garner(A,M); } return ret; } template vector<__int128_t> convolution_i128(const vector &A,const vector &B){ //10^25に収まる範囲. int siza = A.size(),sizb = B.size(),sizc = siza+sizb-1; if(siza == 0 || sizb == 0) return {}; vector<__int128_t> ret(sizc); if(min(siza,sizb) <= 200){ //naive 200はやばい?. if(siza >= sizb){for(int i=0; i; using mint2 = modint; using mint3 = modint; vector a1(siza),b1(sizb); vector a2(siza),b2(sizb); vector a3(siza),b3(sizb); for(int i=0; i C1 = convolution(a1,b1); for(int i=0; i C2 = convolution(a2,b2); for(int i=0; i C3 = convolution(a3,b3); for(int i=0; i convolution_int(const vector &A,const vector &B){ //intに収まる範囲. if(A.size() == 0 || B.size() == 0) return {}; vector ret; if(min(A.size(),B.size()) <= 60){ ret.resize(A.size()+B.size()-1); for(int i=0; i; vector X(A.size()),Y(B.size()),Z; for(int i=0; i void NTTdoubling(vector &A){ //NTTの原理を忘れているため何やってるのか意味が分からない NTT-friendly専用. //INTT->resize(2倍)->NTTの代わりにcopy->INTT->謎の操作->NTT->push sizeが小さい時は効率悪いらしいよ. int n = A.size(); fftinfo info; vector B = A; INTT(B); mint rot = 1,zeta = info.Zeta[countzero(n)]; for(auto &v : B) v *= rot,rot *= zeta; NTT(B); A.reserve(n<<1); for(auto &v : B) A.push_back(v); } bool isNTTfriendly(long long mod){ if(mod == 998244353 || mod == 754974721 || mod == 16777216 || mod == 469762049) return true; return false; //現状false 原子根求める機能を追加してから. int have2 = countzero(mod-1); return have2 >= 20;//とりあえず2^20でokとする; } } using namespace to_fold; int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); long long N,M; cin >> N >> M >> mod; mint::setmod(mod); if(M > 1000) return 0; vector A(N+1); for(int i=1; i<=N; i++){ long long a; cin >> a; a %= mod; A.at(i) = a; } auto B = A; auto mul = [&](const vector &X,const vector &Y) -> vector { vector ret(N+1); auto C = convolution(X,Y); for(int i=1; i<=N; i++) ret.at(i) = X.at(i)+Y.at(i); for(int i=3; i<=N; i++) for(int k=2; k