#include #include using i64 = long long; template struct Mint { inline static constexpr T mod = MOD; T v; Mint() : v(0) {} Mint(signed v) : v(v) {} Mint(long long t) { v = t % MOD; if (v < 0) v += MOD; } Mint pow(long long k) { Mint res(1), tmp(v); while (k) { if (k & 1) res *= tmp; tmp *= tmp; k >>= 1; } return res; } static Mint add_identity() { return Mint(0); } static Mint mul_identity() { return Mint(1); } Mint inv() { return pow(MOD - 2); } Mint &operator+=(Mint a) { v += a.v; if (v >= MOD) v -= MOD; return *this; } Mint &operator-=(Mint a) { v += MOD - a.v; if (v >= MOD) v -= MOD; return *this; } Mint &operator*=(Mint a) { v = 1LL * v * a.v % MOD; return *this; } Mint &operator/=(Mint a) { return (*this) *= a.inv(); } Mint operator+(Mint a) const { return Mint(v) += a; } Mint operator-(Mint a) const { return Mint(v) -= a; } Mint operator*(Mint a) const { return Mint(v) *= a; } Mint operator/(Mint a) const { return Mint(v) /= a; } Mint operator+() const { return *this; } Mint operator-() const { return v ? Mint(MOD - v) : Mint(v); } bool operator==(const Mint a) const { return v == a.v; } bool operator!=(const Mint a) const { return v != a.v; } }; template std::ostream &operator<<(std::ostream &os, Mint m) { os << m.v; return os; } using Z = Mint; struct Combination { std::vector fac, ifac; int N; Combination(int _N) : N(2 * _N), fac(2 * _N + 1), ifac(2 * _N + 1) { fac[0] = Z(1); for (int i = 1; i <= N; i++) { fac[i] = fac[i - 1] * Z(i); } ifac[N] = fac[N].inv(); for (int i = N - 1; i >= 0; i--) { ifac[i] = ifac[i + 1] * Z(i + 1); } } Z C(int n, int k) { if (n < k or n < 0 or k < 0) { return Z(0); } return fac[n] * ifac[n - k] * ifac[k]; } Z P(int n, int k) { if (n < k or n < 0 or k < 0) { return Z(0); } return fac[n] * ifac[n - k]; } Z H(int n,int k){ return C(n+k-1,n); } Z S(int n,int k){ Z ans=0; for(i64 i=0;i<=k;i++){ if((k-i)%2==0){ ans+=C(k,i)*Z(i).pow(n); } else{ ans-=C(k,i)*Z(i).pow(n); } } return ans*ifac[k]; } }; const int N=3e6; std::vectorprime; std::vectoris_prime(N+1,true); std::vectormobius(N+1,1); void sieve(){ is_prime[0]=is_prime[1]=false; for(int p=2;p<=N;p++){ if(!is_prime[p])continue; prime.push_back(p); mobius[p]=-1; for(int q=2*p;q<=N;q+=p){ is_prime[q]=false; if((q/p)%p==0)mobius[q]=0; else mobius[q]=-mobius[p]; } } } template std::vector fast_zeta(std::vectorF){ int n=F.size(); for(int p=2;p=1;k--){ F[k]+=F[k*p]; } } return F; } template std::vector fast_mobius(std::vectorf){ int n=f.size(); for(int p=2;p std::vector gcd_conv(const std::vector&f,const std::vector&g){ int n=std::max(f.size(),g.size()); auto F=fast_zeta(f); auto G=fast_zeta(g); std::vectorH(n); for(int i=1;i>H>>W; Z ans=Z(H)*Z(W-1)+Z(W)*Z(H-1); int n=std::max(H,W); std::vectorh(N),w(N); for(int i=0;isync_with_stdio(false); sieve(); solve(); }