求めたいものは \(f(x)\)を

\[ f(x)= \Bigl(1+A_1x+A_1^2x^2+\cdots+A_1^{B_1}x^{B_1}\Bigr) \Bigl(1+A_2x+A_2^2x^2+\cdots+A_2^{B_2}x^{B_2}\Bigr) \cdots \Bigl(1+A_Nx+A_N^2x^2+\cdots+A_N^{B_N}x^{B_N}\Bigr) \]

で定めた時の \(f(x)\) の \(x^M\) の係数を \(998244353\) で割った余りです。 このままでは係数を求めるのが難しいので、まず、式を

\[ f(x)=\frac{\bigl(1-(A_1x)^{B_1+1}\bigr)\bigl(1-(A_2x)^{B_2+1}\bigr)\cdots\bigl(1-(A_Nx)^{B_N+1}\bigr)}{(1-A_1x)(1-A_2x)\cdots (1-A_Nx)} \]

と書き直し,

\[ \frac{1}{(1-A_1x)(1-A_2x)\cdots (1-A_Nx)} =\frac{c_1}{1-A_1x}+ \frac{c_2}{1-A_2x}+\cdots+ \frac{c_N}{1-A_Nx} \]

をみたす係数 \(c_1\), \(\ldots\), \(c_N\) を求めることを考えます。 分母を払うと、

\[ 1 = c_1(1-A_2x)(1-A_3x)\cdots (1-A_Nx) +c_2(1-A_1x)(1-A_3x)\cdots (1-A_Nx) +\cdots +c_N(1-A_1x)(1-A_2x)\cdots (1-A_{N-1}x) \]

となります。 ここで, 両辺に \(x=A_1^{-1},A_2^{-1},\ldots,A_N^{-1}\) を代入する事を考えます。 \(x=A_i^{-1}\) とすると、右辺の \((1-A_ix)\)を含む項はすべて \(0\) になることから, \(c_i=\Bigl ((1-A_1A_i^{-1})\cdots(1-A_{i-1}A_i^{-1}) (1-A_{i+1}A_i^{-1})\cdots (1-A_NA_i^{-1}) \Bigr)^{-1}\) とすれば \(x={A_i}^{-1}\)において両辺は一致します。 ここで、\(A_i\)はどの \(2\) つも互いに異なる事から, \(c_i\)は有限値の有理数となっていることに注意します。さて、\(c_1,\ldots, c_N\)をそのようにして求めて代入したとき, \((左辺)-(右辺)\)は高々 \((N-1)\) 次式であり, \(x=A_1^{-1},A_2^{-1},\ldots,A_N^{-1}\) の相異なる \(N\) 点で \(0\) となる事から, 両辺が多項式として一致している事が分かります。 ここで、各\(A_i\)は \(1\)以上 \(998244353\) 未満であった事から, \(\bmod{ 998244353}\) における逆元\(A_i^{-1}\)を持ち、\(c_i\) は分子・分母のどちらも \(\bmod{998244353}\)で \(0\) となる事はなく、\(c_i\) を \(\bmod{998244353}\) で求めることができます。このとき、

\[ 1 \equiv c_1(1-A_2x)(1-A_3x)\cdots (1-A_Nx) +c_2(1-A_1x)(1-A_3x)\cdots (1-A_Nx) +\cdots +c_N(1-A_1x)(1-A_2x)\cdots (1-A_{N-1}x) \pmod{998244353} \]

となります。

さて、このとき \( f(x) \equiv \bigl(1-(A_1x)^{B_1+1}\bigr)\bigl(1-(A_2x)^{B_2+1}\bigr)\cdots\bigl(1-(A_Nx)^{B_N+1}\bigr) \bigl( c_1(1+A_1x+(A_1x)^2+\cdots) +c_2(1+A_2x+(A_2x)^2+\cdots) +\cdots +c_N(1+A_Nx+(A_Nx)^2+\cdots) \bigr) \pmod{998244353} \) と書けます。 左の

\[ \bigl(1-(A_1x)^{B_1+1}\bigr)\bigl(1-(A_2x)^{B_2+1}\bigr)\cdots\bigl(1-(A_Nx)^{B_N+1}\bigr) \]

の部分は高々 \(2^N\) 項からなります。このうち 一つの項を取って来て, \(d_kx^k\) であったとき, \(k>M\) ならばこれと 右側の部分の積の結果として次数が下がる事は無いので考える必要がありません。 そうでないとき, \(d_kx^k\bigl( c_1(1+A_1x+(A_1x)^2+\cdots) +c_2(1+A_2x+(A_2x)^2+\cdots) +\cdots +c_N(1+A_Nx+(A_Nx)^2+\cdots) \bigr)\)の \(x^M\)の係数は \(d_k\bigl( c_1A_1^{M-k}+c_2A_2^{M-k}\cdots +c_NA_N^{M-k} \bigr)\) で求められます。これを\(2^N\) 項それぞれに対して計算すると計算量は \(O(2^N\cdot N\log M)\) であり、 これ以外のパートも\(d_i\)の計算に \(O(N\log(B_i)+2^N)\)、\(c_i\)を求めるのに\(O(N(N+\log P))\) (今回は\(P=998244353\)) である事から、十分に間に合います。 よって、この問題を解く事が出来ました。 実装時のオーバーフローにはよく気を付けてください。

ちなみに、無限項を扱いたくないという人は\(f(x)\)を \(c_i\) を用いて表すときに\(\Sigma_{i=1}^n c_i\bigl(1+A_ix+(A_ix)^2+\cdots +(A_ix)^{B_i}) \bigl(1-(A_1x)^{B_1+1}\bigr)\bigl(1-(A_2x)^{B_2+1}\bigr)\cdots \bigl(1-(A_{i-1}x)^{B_{i-1}+1}\bigr)\bigl(1-(A_{i+1}x)^{B_{i+1}+1}\bigr) \cdots\bigl(1-(A_Nx)^{B_N+1}\bigr)\) と書いても同様に \(O(2^N\cdot N\log M)\)で計算できます。

c++による実装例 :

#include <bits/stdc++.h>
using namespace std;

#define N 16
#define MOD 998244353
#define ll long long
#define rep(i, n) for(int i = 0; i < n; ++i)

ll modpow(ll x, ll k) {
	ll re = 1;
	while (k > 0) {
		if (k & 1)re = (re*x) % MOD;
		k = (k >> 1);
		x = (x*x) % MOD;
	}
	return re;
}

ll rev(ll x) { return modpow(x, MOD - 2); }

int main() {
	int n;
	ll m;
	ll a[N], b[N];
	ll c[N];
	ll d[(1 << N)], p[(1 << N)];
	ll x, y;
	ll ans = 0;

	cin >> n >> m;
	d[0] = 1LL;
	p[0] = 0LL;

	rep(i, n) {
		cin >> a[i] >> b[i];
		b[i]++;
		x = (MOD - modpow(a[i], b[i])) % MOD;
		rep(j, (1 << i)) {
			d[(1 << i) + j] = (d[j] * x) % MOD;
			p[(1 << i) + j] = p[j] + b[i];
		}
	}

	rep(i, n) {
		x = rev(a[i]);
		c[i] = 1LL;
		rep(j, n) {
			if (j != i) {
				y = (a[j] * x) % MOD;
				c[i] = (c[i] * (MOD + 1 - y)) % MOD;
			}
		}
		c[i] = rev(c[i]);
	}

	rep(i, (1 << n)) {
		if (p[i] <= m) {
			x = 0;
			rep(j, n) {
				x = (x + (modpow(a[j], m - p[i])*c[j])) % MOD;
			}
			ans = (ans + (x*d[i])) % MOD;
		}
	}

	cout << ans << endl;
	return 0;
}