#include #include #include #include using namespace std; typedef long long ll; typedef pair P; typedef pair T; typedef pair Ps; long long int INF = 2e18; const ll fact_table = 3200008; double Pi = 3.1415926535897932384626; priority_queue pql; priority_queue

pqp; priority_queue

bag; //big priority queue priority_queue ,greater > pqls; priority_queue ,greater

> pqps; //small priority queue //top pop ll dx[8]={1,0,-1,0,1,1,-1,-1}; ll dy[8]={0,1,0,-1,1,-1,-1,1}; char dir[] = "DRUL"; //↓,→,↑,← #define endl "\n" #ifdef ENJAPMA #undef endl #endif #define p(x) cout< &a, bool rev = false) { ll N = a.size(), h = 0; for (ll i = 0; 1 << i < N; i++) h++; for (ll i = 0; i < N; i++) { ll j = 0; for (ll k = 0; k < h; k++) j |= (i >> k & 1) << (h - 1 - k); if (i < j) swap(a[i], a[j]); } for (ll i = 1; i < N; i *= 2) { ll base = mypow(root, (m - 1) / i / 2, m); if (rev) base = mypow(base, m - 2, m); ll w = 1; for (ll j = 0; j < i; j++) { for (ll k = 0; k < N; k += i*2) { ll s = a[j+k], t = a[j+k+i] * w % m; a[j+k+0] = (s + t) % m; a[j+k+i] = (s - t + m) % m; } w = w * base % m; } } if (rev) { ll tmp = mypow(N, m-2, m); for(ll &v : a) v = v * tmp % m; } } //(1012924417, 5), (924844033, 5) vector conv(ll _mod, ll root, const vector &a, const vector &b) { ll s = 1, t = a.size() + b.size() - 1; while(s < t) s *= 2; vector F(s), G(s); for(ll i = 0; i < (ll)a.size(); i++) F[i] = a[i]; for(ll i = 0; i < (ll)b.size(); i++) G[i] = b[i]; DFT(_mod, root, F); DFT(_mod, root, G); for(ll i = 0; i < s; i++) F[i] = (ll)F[i] * G[i] % _mod; DFT(_mod, root, F, true); return F; } }; // auto res = NTT::conv(mod, 3ll, atable, btable); ll fact[fact_table + 5],rfact[fact_table + 5]; void c3_init(){ fact[0] = rfact[0] = 1; for(ll i=1; i<=fact_table; i++){ fact[i] = (fact[i-1]*i) % mod; } rfact[fact_table] = mypow(fact[fact_table],mod - 2, mod); for(ll i=fact_table; i>=1; i--){ rfact[i-1] = rfact[i] * i; rfact[i-1] %= mod; } return;} ll c3(ll n,ll r){ return (((fact[n] * rfact[r]) % mod ) * rfact[n-r]) % mod;} bool multicase = false; ll n,m,num,a,b,c,d,e,h,q; ll w, k, ans; ll x[500005], y[500005]; vector G[500005]; void calc(ll l, ll r){ // [l, r) の範囲を分割統治する if(l == r)return; if(l == r - 1)return; ll mid = (l + r) / 2; calc(l, mid); calc(mid, r); G[l] = NTT::conv(mod, 3ll, G[l], G[mid]); return; } void solve(){ c3_init(); cin >> n >> q; for(ll i=0;i> x[i]; G[i].pb(1); G[i].pb(x[i] - 1); } for(ll i=0;i> y[i]; } calc(0, n); for(ll i=0;i> q; }else{ q = 1; } while(q--){ // pu("Case ");pu("#");pu(testcase);pu(": "); solve(); testcase++; } // solve(); return 0; }