正整数列 \(A=(A _ 1,A _ 2,\ldots,A _ N)\) と正整数 \(M\) に対して、この問題の答えを \(f(A,M)\) と書くことにします。

また、長さの等しい非負整数列 \(A=(A _ 1,A _ 2,\ldots,A _ N),B=(B _ 1,B _ 2,\ldots,B _ N)\) に対して \(A\times B\) で非負整数 \(\displaystyle\sum _ {i=1} ^ NA _ iB _ i\) を、\(A+B\) で非負整数列 \((A _ 1+B _ 1,A _ 2+B _ 2,\ldots,A _ N+B _ N)\) を表すことにします。 また、非負整数列 \(A=(A _ 1,A _ 2,\ldots,A _ N)\) と非負整数 \(c\) に対して \(cA\) で非負整数列 \((cA _ 1,cA _ 2,\ldots,cA _ N)\) を表すことにします。

任意の \(A,B,C,x,y\) に対して \(A\times(xB+yC)=x(A\times B)+y(A\times C)\) が成り立つことなどに注意してください。

正整数 \(d\) をとると、任意の非負整数列 \(X=(X _ 1,X _ 2,\ldots,X _ N)\) に対して次の条件を満たす非負整数列 \(Q=(Q _ 1,Q _ 2,\ldots,Q _ N),R=(R _ 1,R _ 2,\ldots,R _ N)\) が一意に存在します。

• \(X=dQ+R\)
• \(0\le R _ i\lt d\ (1\le i\le N)\)

よって、非負整数列 \(X\) のうち条件を満たすものを数え上げることは、非負整数列の組 \((Q,R)\) のうち（適当に書き換えた）条件を満たすものを数え上げることに対応させることができます。

求めたいものは \(A\times X\leq M\) なる \(X\) の個数だったので、\(d(A\times Q)+A\times R\leq M\) なる組 \((Q,R)\) の個数を数えることを考えます。 すべての要素が \(0\) 以上 \(d\) 未満であるような列 \(R\) 全体に対する \(A\times R\) の値の多重集合を \(S\) とすると、\[f(A,M)=\sum _ {s\in S}f\!\left(\!A,\left\lfloor\dfrac{M-s}d\right\rfloor\right)\] が成り立ちます。

整数で添字付けられた非負整数の集合 \(\lbrace c _ i\rbrace _ {i\in\mathbb Z}\) であって \(c _ i\ne 0\) なる \(i\) がたかだか有限個であるものに対して、\(\displaystyle\sum _ {i\in\mathbb Z}c _ if(A,i)\) の形で書ける式の値を求めることを考えます。 これは、上の関係を用いて \[\begin{aligned}\sum _ {i\in\mathbb Z}c _ if(A,i)&=\sum _ {i\in\mathbb Z}c _ i\sum _ {s\in S}f\!\left(\!A,\left\lfloor\dfrac{i-s}d\right\rfloor\right)\\&=\sum _ {i\in\mathbb Z}\left(\sum _ {j=0} ^ {d-1}\sum _ {s\in S}c _ {id+j+s}\right)f(A,i)\end{aligned}\] と書くことができます。

\(\displaystyle\sum _ {j=0} ^ {d-1}\sum _ {s\in S}c _ {id+j+s}\) を改めて \(\lbrace c _ i\rbrace _ {i\in\mathbb Z}\) とする操作を考えます。 \(\lbrace c _ i\rbrace\) および \(S\) を適切に管理することで、\(\displaystyle L _ 0\coloneqq\max _ {c _ i\ne0}i-\min _ {c _ i\ne0}i,L _ 1\coloneqq\max _ {s\in S}s\) として、\(O((L _ 0+L _ 1)\log(L _ 0+L _ 1))\) 時間でこの操作を行うことができます。 \(c _ i\ne0\) なる最大の \(i\) は一回の操作で \(\dfrac1d\) 倍以下になるので、\(c _ M=1,c _ i=0\ (i\ne M)\) から操作を \(\lceil\log _ dM\rceil\) 回繰り返すことで \(c _ i\ne0\) なる \(i\) を \(i\le0\) に限ることができます。 \(f(A,i)=0\ (i\lt0)\) および \(f(A,0)=1\) なので、このようになった時点での \(c _ 0\) が求める値となります。

明らかに \(\displaystyle L _ 1=(d-1)\sum _ iA _ i\) です。 \(c _ M=1,c _ i=0\ (i\ne M)\) から上の操作を繰り返したとき、つねに \(L _ 0\le L _ 1\dfrac d{d-1}\) が成り立つことが示せるので、\(L _ 0+L _ 1\le(2d-1)\displaystyle\sum _ iA _ i\) が成り立ちます。 よって、適当な（\(2\) 以上の）正整数 \(d\) を選ぶことで十分高速に問題を解くことができます。

実装例は以下のようになります。 以下の実装例では \(S\) の情報を求めるのに \(O(d ^ 2\max A _ i\sum A _ i\log(d\sum A _ i))\) 時間ほどかけていますが、適切に実装することでより高速に求めることができます（が、この実装でも十分高速です）。

#include <iostream>
#include <vector>
#include <ranges>
#include <atcoder/convolution>

int main() {
    using namespace std;
    using modint = atcoder::static_modint<998244353>;
    unsigned N;
    unsigned long M;
    cin >> N >> M;
    constexpr unsigned d{2};
    vector<modint> S{1}; // S[i] = 0 以上 d 未満の非負整数列 x のうち i = ∑ A_jx_j なるものの個数
    for (const auto A : views::istream<unsigned>(cin)) {
        vector<modint> tmp(A * (d - 1) + 1);
        for (auto&& t : tmp | views::chunk(A))
            t[0] = 1;
        S = convolution(move(S), move(tmp));
    }
    vector<modint> coef{1}; // ∑ coef[M - i]f(A, i) が答えとなるように管理
    while (M) {
        vector<modint> result(M / d - (M - min(M, size(S) + size(coef) - 2)) / d + 1);
        for (const auto& [x, i] : views::zip(convolution(S, coef), views::iota(0)) // 畳み込んで
                                | views::take(M + 1)) // 負に対応する部分は消しておく
            result[M / d - (M - i) / d] += x;
        swap(coef, result);
        M /= d;
    }
    cout << coef.front().val() << endl; // coef[0] が答え
    return 0;
}