// from 0:15 #include #define rep(i,n) for(int i = 0; i < (n); ++i) #define rep1(i,n) for(int i = 1; i <= (n); ++i) #define drep(i,n) for(int i = (n)-1; i >= 0; --i) #define srep(i,s,t) for (int i = s; i < (t); ++i) #define rng(a) a.begin(),a.end() #define rrng(a) a.rbegin(),a.rend() #define fi first #define se second #define pb push_back #define eb emplace_back #define pob pop_back #define sz(x) (int)(x).size() #define pcnt __builtin_popcountll #define snuke srand((unsigned)clock()+(unsigned)time(NULL)); #define newline puts("") using namespace std; template using vc = vector; template using vv = vc>; template using PQ = priority_queue,greater>; using uint = unsigned; using ull = unsigned long long; using vi = vc; using vvi = vv; using vvvi = vv; using ll = long long; using vl = vc; using vvl = vv; using vvvl = vv; using P = pair; using vp = vc

; using vvp = vv

; int geti(){int x;scanf("%d",&x);return x;} vi pm(int n, int s=0) { vi a(n); iota(rng(a),s); return a;} templateistream& operator>>(istream&i,vc&v){rep(j,sz(v))i>>v[j];return i;} templatestring join(const T&v,const string& d=""){stringstream s;rep(i,sz(v))(i?s<ostream& operator<<(ostream&o,const vc&v){if(sz(v))o<istream& operator>>(istream&i,pair&v){return i>>v.fi>>v.se;} templateostream& operator<<(ostream&o,const pair&v){return o<void operator--(pair&a,int){a.fi--;a.se--;} templatevoid operator--(vc&a,int){for(T&x:a)x--;} templatevoid operator++(vc&a,int){for(T&x:a)x++;} templatevoid operator+=(vc&a,T b){for(T&x:a)x+=b;} templatevoid operator+=(vc&a,const vc&b){a.insert(a.end(),rng(b));} templatebool mins(T1& x,const T2&y){if(x>y){x=y;return true;}else return false;} templatebool maxs(T1& x,const T2&y){if(xTx dup(Tx x, Ty y){return (x+y-1)/y;} templatell suma(const vc&a){ll res(0);for(auto&&x:a)res+=x;return res;} templatell suma(const vv&a){ll res(0);for(auto&&x:a)res+=suma(x);return res;} templatevoid uni(T& a){sort(rng(a));a.erase(unique(rng(a)),a.end());} templatevoid prepend(vc&a,const T&x){a.insert(a.begin(),x);} const double eps = 1e-10; const ll LINF = 1001002003004005006ll; const int INF = 1001001001; #define dame { puts("-1"); return;} #define yes { puts("Yes"); return;} #define no { puts("No"); return;} #define ret(x) { cout<<(x)<=mod) x-=mod; return *this;} mint& operator-=(const mint& a) { if((x+=mod-a.x)>=mod) x-=mod; return *this;} mint& operator*=(const mint& a) { x=(ull)x*a.x%mod; return *this;} mint& operator/=(const mint& a) { x=(ull)x*a.pow(mod-2).x%mod; return *this;} mint operator+(const mint& a) const { return mint(*this) += a;} mint operator-(const mint& a) const { return mint(*this) -= a;} mint operator*(const mint& a) const { return mint(*this) *= a;} mint operator/(const mint& a) const { return mint(*this) /= a;} mint pow(ll t) const { mint res = 1; for (mint p=x;t;p*=p,t>>=1) if (t&1) res *= p; return res; } mint ppow(ll t) const { int p=mod-1; return pow((t%p+p)%p);} bool operator<(const mint& a) const { return x < a.x;} bool operator==(const mint& a) const { return x == a.x;} bool operator!=(const mint& a) const { return x != a.x;} }; mint ex(mint x, ll t) { return x.pow(t);} istream& operator>>(istream&i,mint&a) {i>>a.x;return i;} //* ostream& operator<<(ostream&o,const mint&a) {o< y+i) a = s?-y:y, b = i; } o<; using vvm = vector; struct modinv { int n; vm d; modinv(): n(2), d({0,1}) {} mint operator()(int i) { while (n <= i) d.pb(-d[mod%n]*(mod/n)), ++n; return d[i];} mint operator[](int i) const { return d[i];} } invs; struct modfact { int n; vm d; modfact(): n(2), d({1,1}) {} mint operator()(int i) { while (n <= i) d.pb(d.back()*n), ++n; return d[i];} mint operator[](int i) const { return d[i];} } facs; struct modfactinv { int n; vm d; modfactinv(): n(2), d({1,1}) {} mint operator()(int i) { while (n <= i) d.pb(d.back()*invs(n)), ++n; return d[i];} mint operator[](int i) const { return d[i];} } ifacs; mint comb(int a, int b) { if (a < b || b < 0) return 0; return facs(a)*ifacs(b)*ifacs(a-b); } // struct NTT { int ceil_pow2(int n) { int x = 0; while ((1U<> cnt2), ie = ~e; for (int i = cnt2; i >= 2; i--) { es[i - 2] = e; ies[i - 2] = ie; e *= e; ie *= ie; } mint now = 1; rep(i,cnt2-1) sum_e[i] = es[i] * now, now *= ies[i]; } rep1(ph,h) { int w = 1<<(ph-1), p = 1<<(h-ph); mint now = 1; rep(s,w) { int offset = s << (h - ph + 1); for (int i = 0; i < p; i++) { auto l = a[i + offset], r = a[i + offset + p] * now; a[i + offset] = l + r; a[i + offset + p] = l - r; } now *= sum_e[bsf(~(uint)(s))]; } } } void butterfly_inv(vm& a) { static mint g = _g; int n = sz(a), h = ceil_pow2(n); static bool first = true; static mint sum_ie[30]; if (first) { first = false; mint es[30], ies[30]; int cnt2 = bsf(mod - 1); mint e = g.pow((mod - 1) >> cnt2), ie = ~e; for (int i = cnt2; i >= 2; i--) { es[i - 2] = e; ies[i - 2] = ie; e *= e; ie *= ie; } mint now = 1; rep(i,cnt2-1) sum_ie[i] = ies[i] * now, now *= es[i]; } for (int ph = h; ph >= 1; ph--) { int w = 1 << (ph - 1), p = 1 << (h - ph); mint inow = 1; rep(s,w) { int offset = s << (h - ph + 1); for (int i = 0; i < p; i++) { auto l = a[i + offset], r = a[i + offset + p]; a[i + offset] = l + r; a[i + offset + p] = (ull)(mod + l.x - r.x) * inow.x; } inow *= sum_ie[bsf(~(uint)(s))]; } } } vm operator()(vm a, vm b) { int n = sz(a), m = sz(b); if (!n || !m) return {}; if (min(n, m) <= 60) { if (n < m) swap(n, m), swap(a, b); vm ans(n+m-1); rep(i,n)rep(j,m) ans[i + j] += a[i] * b[j]; return ans; } int z = 1 << ceil_pow2(n+m-1); a.resize(z); butterfly(a); b.resize(z); butterfly(b); rep(i,z) a[i] *= b[i]; butterfly_inv(a); a.resize(n + m - 1); mint iz = ~(mint(z)); rep(i,n+m-1) a[i] *= iz; return a; } } ntt; struct fps : vm { #define d (*this) #define s int(vm::size()) template fps(Args...args): vm(args...) {} fps(initializer_list a): vm(rng(a)) {} int size() const { return vm::size();} void rsz(int n) { if (s < n) resize(n);} fps& low_(int n) { resize(n); return d;} fps low(int n) const { return fps(d).low_(n);} fps low(fps a, int n) const { return a.low_(n);} fps& rev_() { reverse(rng(d)); return d;} fps rev() const { return fps(d).rev_();} fps rev(fps a) const { return a.rev_();} fps odd(int si=1) const { fps r(s/2); for(int i=si;i>1]=d[i]; return r;} mint& operator[](int i) { rsz(i+1); return vm::operator[](i);} mint operator[](int i) const { return i>(int a) const { fps r(d); r.rsz(a); r.erase(r.begin(), r.begin()+a); return r;} fps& fit() { while (s && !back().x) pop_back(); return d;} fps operator-() const { fps r(d); rep(i,s) r[i] = -r[i]; return r;} fps& operator+=(const fps& a) { rsz(sz(a)); rep(i,sz(a)) d[i] += a[i]; return d;} fps& operator-=(const fps& a) { rsz(sz(a)); rep(i,sz(a)) d[i] -= a[i]; return d;} fps& operator*=(const fps& a) { return d = ntt(d, a);} fps& operator/=(const fps& a) { int w = s-sz(a)+1; if (w <= 0) return d = 0; return (rev_().low_(w) *= a.rev().inv(w)).low_(w).rev_(); } fps& operator%=(const fps& a) { return (d -= d/a*a).low_(sz(a)-1);} fps& operator*=(mint a) { rep(i,s) d[i] *= a; return d;} fps& operator/=(mint a) { return d *= ~a;} fps& operator*=(int a) { return d *= mint(a);} fps& operator/=(int a) { return d /= mint(a);} fps operator+(const fps& a) const { return fps(d) += a;} fps operator-(const fps& a) const { return fps(d) -= a;} fps operator*(const fps& a) const { return fps(d) *= a;} fps operator/(const fps& a) const { return fps(d) /= a;} fps operator%(const fps& a) const { return fps(d) %= a;} fps operator*(mint a) const { return fps(d) *= a;} fps operator/(mint a) const { return fps(d) *= ~a;} fps operator*(int a) const { return fps(d) *= mint(a);} fps operator/(int a) const { return fps(d) /= mint(a);} fps& mul1(mint a) { pb(0); drep(i,s-1) d[i+1] += d[i], d[i] *= a; return d;} // *=(x+a), /=(x+a) fps& div1(mint a) { mint pre = back(); pop_back(); drep(i,s) std::swap(pre, d[i]), pre -= d[i]*a; return d;} fps dif() const { fps r(s-1); rep1(i,sz(r)) r[i-1] = d[i]*i; return r;} fps integ() const { fps r(s+1); rep1(i,s) r[i] = d[i-1]*invs(i); return r;} fps inv() const { return inv(s);} fps inv(int w) const { fps r({~d[0]}); for (int i = 1; i < w; i <<= 1) r = r*2 - low(r*r*low(i<<1), i<<1); return r.low_(w); } // [fps_nth] // [fps_multipointeval] // [fps_taylorshift] // [fps_combconv] #undef s #undef d }; struct Solver { void solve() { int n,m; scanf("%d%d",&n,&m); vp a(n); rep(i,n) cin>>a[i].fi; rep(i,n) cin>>a[i].se; vvm d(m,vm(M2,1)); rep(si,m) { for (int i = si; i < n; i += m) { auto [l,r] = a[i]; fps x; rep(j,l+r+1) x[M+(r-j)] = comb(l+r,j); rep(j,M2) d[si][j] *= x[j]; } } queue q; rep(i,m) q.emplace(d[i]); while (sz(q) > 1) { fps a = q.front(); q.pop(); fps b = q.front(); q.pop(); q.push(a*b); } cout<