#include #include using namespace std; const int MOD = 998244353; long long modPow(long long a, long long p){ if(p == 0) return 1; auto res = modPow(a, p/2); res = (res*res)%MOD; if(p%2) res = (res*a)%MOD; return res; } long long calcInv(long long a){ return modPow(a, MOD-2); } void ntt(vector& v, int inv){ const int n = v.size(); auto w = modPow(3, (MOD-1)/n); if(inv == -1) w = calcInv(w); int rev = 0; for(int i=1;i(rev^=j);j/=2); if(i < rev) swap(v[i], v[rev]); } for(int m=1;m convolution(const vector& a, const vector& b){ int _n = a.size() + b.size(); int n = 1; while(n < _n) n *= 2; vector na(n, 0), nb(n, 0); for(int i=0;i seen(P, 0); bool ok = true; long long cur = 1; for(int j=0;j> P){ vector g(P-1); const int r = getPrimitiveRoot(P); int m = 1; for(int i=0;i A(P-1), B(P-1); for(int i=0;i> A[g[i]]; for(int i=0;i> B[g[i]]; auto v = convolution(A, B); vector res(P-1); m = 1; for(int i=0;i