#include using namespace std; //ModInt begin const int mod=1e9+7; //const int mod=998244353; static constexpr uint32_t mul_inv(uint32_t n, int e = 5, uint32_t x = 1) { return e == 0 ? x : mul_inv(n, e - 1, x * (2 - x * n)); } template< uint32_t mod,bool friendly, bool fast = false > struct ModInt { using u32 = uint32_t; using u64 = uint64_t; static constexpr u32 inv_ = mul_inv(mod); static constexpr u32 r2 = -uint64_t(mod) % mod; uint32_t x; ModInt() : x(0) {} ModInt(const int64_t &y) : x(reduce(u64(fast ? y : (y >= 0 ? y % mod : (mod - (-y) % mod) % mod)) * r2)) {} u32 reduce(const u64 &w) const { return u32(w >> 32) + mod - u32((u64(u32(w) * inv_) * mod) >> 32); } ModInt &operator+=(const ModInt &p) { if(int(x += p.x - 2 * mod) < 0) x += 2 * mod; return *this; } ModInt &operator-=(const ModInt &p) { if(int(x -= p.x) < 0) x += 2 * mod; return *this; } ModInt &operator*=(const ModInt &p) { x = reduce(uint64_t(x) * p.x); return *this; } ModInt &operator/=(const ModInt &p) { *this *= p.inv(); return *this; } ModInt operator-() const { return ModInt() - *this; } ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; } ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; } ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; } ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; } bool operator==(const ModInt &p) const { return val() == p.val(); } bool operator!=(const ModInt &p) const { return val() != p.val(); } int val() const { return reduce(x) % mod; } ModInt pow(int64_t n) const { ModInt ret(1), mul(*this); while(n > 0) { if(n & 1) ret *= mul; mul *= mul; n >>= 1; } return ret; } ModInt inv() const { return pow(mod - 2); } /* friend ModInt operator+(const ModInt& lhs,const ModInt& rhs){ return ModInt(lhs)+=rhs; } friend ModInt operator-(const ModInt& lhs,const ModInt& rhs){ return ModInt<>(lhs)-=rhs; } friend ModInt operator*(const ModInt& lhs,const ModInt& rhs){ return ModInt(lhs)*=rhs; } friend ModInt operator/(const ModInt& lhs,const ModInt& rhs){ return ModInt(lhs)/=rhs; } friend bool operator==(const ModInt& lhs,const ModInt& rhs){ return lhs.val()==rhs.val(); } friend bool operator!=(const ModInt& lhs,const ModInt& rhs){ return lhs.val()!=rhs.val(); } */ friend ostream &operator<<(ostream &os, const ModInt &p) { return os << p.val(); } friend istream &operator>>(istream &is, ModInt &a) { int64_t t; is >> t; a = ModInt< mod, friendly,fast >(t); return (is); } static int get_mod() { return mod; } static bool is_friendly() {return friendly;} }; using mint = ModInt< mod,false>;//負数を使う際はfastをtrueにしないように注意 //ModInt end //mintcomb begin template struct Mintcomb{ private: vector fact,ifact; int sup; public: Mintcomb(int sup_):sup(sup_),fact(vector(sup_)),ifact(vector(sup_)){ fact[0]=Mint(1); for(int i=1;i0;--i)ifact[i-1]=ifact[i]*Mint(i); } mint f(int n){return fact[n];} mint invf(int n){return ifact[n];} mint c(int n,int r){ if(n<0||n struct NumberTheoreticTransformFriendlyModInt { vector< Mint > dw, idw; int max_base; Mint root; NumberTheoreticTransformFriendlyModInt() { const unsigned mod = Mint::get_mod(); assert(Mint::is_friendly()); assert(mod >= 3 && mod % 2 == 1); auto tmp = mod - 1; max_base = 0; while(tmp % 2 == 0) tmp >>= 1, max_base++; root = 2; while(root.pow((mod - 1) >> 1) == 1) root += 1; assert(root.pow(mod - 1) == 1); dw.resize(max_base); idw.resize(max_base); for(int i = 0; i < max_base; i++) { dw[i] = -root.pow((mod - 1) >> (i + 2)); idw[i] = Mint(1) / dw[i]; } } void ntt(vector< Mint > &a) { const int n = (int) a.size(); assert((n & (n - 1)) == 0); assert(__builtin_ctz(n) <= max_base); for(int m = n; m >>= 1;) { Mint w = 1; for(int s = 0, k = 0; s < n; s += 2 * m) { for(int i = s, j = s + m; i < s + m; ++i, ++j) { auto x = a[i], y = a[j] * w; a[i] = x + y, a[j] = x - y; } w *= dw[__builtin_ctz(++k)]; } } } void intt(vector< Mint > &a, bool f = true) { const int n = (int) a.size(); assert((n & (n - 1)) == 0); assert(__builtin_ctz(n) <= max_base); for(int m = 1; m < n; m *= 2) { Mint w = 1; for(int s = 0, k = 0; s < n; s += 2 * m) { for(int i = s, j = s + m; i < s + m; ++i, ++j) { auto x = a[i], y = a[j]; a[i] = x + y, a[j] = (x - y) * w; } w *= idw[__builtin_ctz(++k)]; } } if(f) { Mint inv_sz = Mint(1) / n; for(int i = 0; i < n; i++) a[i] *= inv_sz; } } vector< Mint > multiply(vector< Mint > a, vector< Mint > b) { int need = a.size() + b.size() - 1; int nbase = 1; while((1 << nbase) < need) nbase++; int sz = 1 << nbase; a.resize(sz, 0); b.resize(sz, 0); ntt(a); ntt(b); Mint inv_sz = Mint(1) / sz; for(int i = 0; i < sz; i++) a[i] *= b[i] * inv_sz; intt(a, false); a.resize(need); return a; } }; #define NTT NumberTheoreticTransformFriendlyModInt //ntt end //any_mod_ntt begin template< int mod > vector< int > AnyModNTTMultiply(vector< int > &a, vector< int > &b) { using mint = ModInt< mod ,false>; using mint1 = ModInt< 1045430273 ,true>; using mint2 = ModInt< 1051721729 ,true>; using mint3 = ModInt< 1053818881 ,true>; NumberTheoreticTransformFriendlyModInt< mint1 > ntt1; NumberTheoreticTransformFriendlyModInt< mint2 > ntt2; NumberTheoreticTransformFriendlyModInt< mint3 > ntt3; vector< mint1 > a1(begin(a), end(a)), b1(begin(b), end(b)); vector< mint2 > a2(begin(a), end(a)), b2(begin(b), end(b)); vector< mint3 > a3(begin(a), end(a)), b3(begin(b), end(b)); auto x = ntt1.multiply(a1, b1); auto y = ntt2.multiply(a2, b2); auto z = ntt3.multiply(a3, b3); const int m1 = 1045430273, m2 = 1051721729, m3 = 1053818881; const auto m1_inv_m2 = mint2(m1).inv().val(); const auto m12_inv_m3 = (mint3(m1) * m2).inv().val(); const auto m12_mod = (mint(m1) * m2).val(); vector< int > ret(x.size()); for(int i = 0; i < x.size(); i++) { auto v1 = ((mint2(y[i]) + m2 - x[i].val()) * m1_inv_m2).val(); auto v2 = ((z[i] + m3 - x[i].val() - mint3(m1) * v1) * m12_inv_m3).val(); ret[i] = (mint(x[i].val()) + mint(m1) * v1 + mint(m12_mod) * v2).val(); } return ret; } //any_mod ntt end //ntt_ll begin vector< long long > Multiply_ll(vector< long long > &a, vector< long long > &b) { //using mint = ModInt< mod ,false>; using mint1 = ModInt< 1045430273 ,true>; using mint2 = ModInt< 1051721729 ,true>; using mint3 = ModInt< 1053818881 ,true>; NumberTheoreticTransformFriendlyModInt< mint1 > ntt1; NumberTheoreticTransformFriendlyModInt< mint2 > ntt2; NumberTheoreticTransformFriendlyModInt< mint3 > ntt3; vector< mint1 > a1(begin(a), end(a)), b1(begin(b), end(b)); vector< mint2 > a2(begin(a), end(a)), b2(begin(b), end(b)); vector< mint3 > a3(begin(a), end(a)), b3(begin(b), end(b)); auto x = ntt1.multiply(a1, b1); auto y = ntt2.multiply(a2, b2); auto z = ntt3.multiply(a3, b3); const __int128 m1 = 1045430273, m2 = 1051721729, m3 = 1053818881; const __int128 m1_inv_m2 = mint2(m1).inv().val(); const __int128 m12_inv_m3 = (mint3(m1) * m2).inv().val(); const __int128 m12 = m1 * m2; vector< long long > ret(x.size()); for(int i = 0; i < x.size(); i++) { __int128 v1 = ((mint2(y[i]) + m2 - x[i].val()) * m1_inv_m2).val(); __int128 v2 = ((z[i] + m3 - x[i].val() - mint3(m1) * v1) * m12_inv_m3).val(); ret[i] = (__int128)(x[i].val()) + m1 * v1 + m12 * v2; } return ret; } //ntt_ll end template//is_ll :型がmintでないならtrue ,upper 型がlong long型出ない場合の上限値 multiply(つまり畳み込み時に用いる) struct fps{ vector coef; fps(){coef.resize(1,1);} fps(vector v){coef=v;} fps operator-()const{ fps res(coef); for(auto &e :res.coef)e*=-1; return res; } fps &operator+=(const T &c){ for(auto &e :coef)e+=c; return *this; } fps operator+(const T &c){fps f(coef);f+=c;return f;} fps &operator-=(const T &c){ for(auto &e :coef)e-=c; return *this; } fps operator-(const T &c){fps f(coef);f-=c;return f;} fps &operator*=(const T &c){ for(auto &e :coef)e*=c; return *this; } fps operator*(const T &c){fps f(coef);f*=c;return f;} //定数割り算 mintでなければ使用不可 fps &operator/=(const T &c){ assert(!is_ll); assert(c.val()!=0); T cinv=c.inv(); *this*=cinv; return *this; } fps operator/(const T &c){fps f(coef);f/=c;return f;} //小さいほうのサイズに合わせる fps &operator+=(const fps &g){ int n=coef.size(),m=g.coef.size(); for(int i=0;i>=(const int d){ int n=coef.size(); coef.erase(coef.begin(),coef.begin()+min(n,d)); coef.resize(n,0); return *this; } fps operator>>(const int d){fps f(coef);f>>=d;return f;} //(1+cx^d)を掛ける void multiply_inplace(const int d,const T c){ int n=coef.size(); for(int i=n-d-1;i>=0;--i)coef[i+d]+=c*coef[i]; } fps multiply(const int d,const T c){fps res=fps(coef);res.multiply_inplace(d,c);return res;} //(1+cx^d)で割る void divide_inplace(const int d,const T c){ int n=coef.size(); for(int i=0;i> g){ int n=coef.size(); auto [d,c]=g.front(); if(d==0)g.erase(g.begin());//定数項は別に扱う else c=0; for(int i=n-1;i>=0;--i){ coef[i]*=c; for(auto &[j,b]:g){ if(j>i)break;//次数昇順 coef[i]+=coef[i-j]*b; } } } fps sparse_multiply(vector> g){fps f=fps(coef);f.sparse_multiply_inplace(g);return f;} //T=min限定 スパースな多項式を掛ける、(次数、係数)の次数昇順なvectorを渡す。 ただし、定数項を持たなければならない(持たない場合は分解して右シフトせよ(z^dで割る)) void sparse_divide_inplace(vector> g){ assert(!is_ll); int n=coef.size(); auto [d,c]=g.front(); assert(d==0&&c!=T(0)); T cinv=c.inv(); g.erase(g.begin()); for(int i=0;ii)break; coef[i]-=coef[i-j]*b; } coef[i]*=cinv; } } fps sparse_divide(vector> g){fps f=f(coef);f.sparse_divide_inplace(g);return f;} //T=mint 限定不定定数0とした積分 はみ出した項は削除されるので必要ならresizeしておくこと。 void integral_inplace(){ int n=coef.size(); coef.insert(coef.begin(),0); coef.pop_back(); vector inv(n); inv[1]=T(1); int mod=T::get_mod(); for(int i=2;i ntt; coef=ntt.multiply(coef,g.coef); } else{ vector f_coef(coef.size()),g_coef(g.coef.size()); for(int i=0;i new_coef=AnyModNTTMultiply(f_coef,g_coef); new_coef.resize(size); for(int i=0;i0){if(n&1){ans*=x;}n>>=1;x*=x;}return ans;} void Main(); int main(){cout<>N; vector p(N); rep(i,N)cin>>p[i]; vector coef(10001,0); fps fps(coef); fps.coef[0]=1; rep(i,N)fps.multiply_inplace(p[i],1); int ans=0; rep(i,10001)if(fps.coef[i])ans++; cout<>N>>K; vector a(N); rep(i,N)cin>>a[i]; vector v(K+5,0); v[0]=mint(1); fps f(v); rep(i,N){ f.multiply_inplace(a[i]+1,-1); f.divide_inplace(1,-1); } cout<>N>>K; vector v(N+1,0); v[0]=mint(1); fps f(v); f<<=1; f.multiply_inplace(K-1,mint(-1)); f.multiply_inplace(1,mint(-1)); f.sparse_divide_inplace(vector>{{0,mint(1)},{1,mint(-2)},{K+1,mint(1)}}); cout<>N; int L[N],R[N]; rep(i,N)cin>>L[i]>>R[i]; vector>> lst(2*N); mint all_prod=1; rep(i,N){ all_prod*=R[i]-L[i]; lst[2*i]={0,{L[i],R[i]}}; lst[2*i+1]={1,{R[i],L[i]}}; } sort(all(lst),[](pair> n1,pair> n2){return n1.second.first v(N+2,0); v[0]=1; fps f(v); int pred=0; int cnt=0;//Lを通過した数 rep(i,2*N){ if(lst[i].first==0){ ++cnt; f*=-lst[i].second.first; f.multiply_inplace(1,mint(-lst[i].second.first).inv()); } else{ if(cnt==N){ fps integral=f.integral(); ans+=integral.eval(pred); ans-=integral.eval(lst[i].second.first); } f/=-lst[i].second.second; f.divide_inplace(1,mint(-lst[i].second.second).inv()); f*=lst[i].second.first-lst[i].second.second; } pred=lst[i].second.first; } ans-=mint(intpow(10,9)-pred)*all_prod; mint fact=1; rep(i,N)fact*=i+2; ans*=fact; cout<>N>>K; vector lst(N+1); lst[0]++; lst[1]--; int L,R; rep(i,K){ cin>>L>>R; lst[L]--; lst[R+1]++; } vector> divlst; rep(i,N+1)if(lst[i]!=0)divlst.push_back({i,mint(lst[i])}); vector v(N+6); v[0]=1; fps f(v); f.multiply_inplace(1,mint(-1)); f.sparse_divide_inplace(divlst); cout<>S; vector v(S+1); v[0]=1; fps f(v); mint ans=0; for(int i=0;i>K; string S;cin>>S; int N=S.size(); vector v(K+1); mint now=1; Mintcomb comb(2000005); rep(i,K+1){ v[i]=comb.c(i+N-1,N-1)*now; now*=25; } fps f(v); f.divide_inplace(1,mint(-26)); cout<>N>>S; vector A(N);rep(i,N)cin>>A[i]; vector v(S+1); v[0]=1; fps f(v); rep(i,N){ f*=mint(2); f.multiply_inplace(A[i],inv2); } cout<>N>>M; vector A(N); vector v(100005); rep(i,N){ cin>>A[i]; ++v[A[i]]; } fps f(v); auto g=f.multiply_ll(f,200005); ll ans=0; for(ll i=200000;i>=0;--i){ if(g.coef[i]<=M){ ans+=i*g.coef[i]; M-=g.coef[i]; } else{ ans+=i*M; M=0; break; } } cout<>N; vector A(N); vector table(P); rep(i,N){ cin>>A[i]; ++table[A[i]]; } vector logtable(P-1); ll now=1; rep(i,P-1){ logtable[i]+=table[now]; now*=2; now%=P; } fps f(logtable); f.multiply_inplace_ll(f,2*P-3); ll ans=0; now=1; rep(i,2*P-3){ ans+=f.coef[i]*now; now*=2; now%=P; } rep(i,N)ans-=A[i]*A[i]%P; cout<>N>>X; vector a(N),v(100001); rep(i,N){ cin>>a[i]; ++v[a[i]]; } fps f(v); f.multiply_inplace_ll(f,2*v.size()-1); ll ans; if(X>f.coef.size()-1)ans=0; else ans=f.coef[X]; cout<>N; vector v(6*N+1); v[0]=1; fps f(v); rep(i,8){ f.multiply_inplace(N+1,-1); f.divide_inplace(1,-1); } cout< sieve; public: Eratosthenes(int n_):n(n_+1),sieve(vector(n,true)){ sieve[0]=sieve[1]=false; int i=2; while(i*i>N; Eratosthenes ers(3*N); vector v(N+1); rep(i,N+1)if(ers.is_prime(i))v[i]=1; fps f(v); auto f2=f.multiply_ll(f,2*N+1); auto f3=f2.multiply_ll(f,3*N+1); ll ans=0; rep(i,3*N+1)if(ers.is_prime(i))ans+=f3.coef[i]; vector v_ev(2*N+1); rep(i,N+1)if(ers.is_prime(i))v_ev[2*i]=1; fps f_ev(v_ev); f_ev.multiply_inplace_ll(f,3*N+1); rep(i,3*N+1)if(ers.is_prime(i))ans-=f_ev.coef[i]*3; cout<