Cake 有 $n$ 种球，编号为 $1$ 到 $n$。其中第 $i$ 种球有无限个（彼此不可区分），且其对应一个代价 $c_i$。Cake 想要带走一些球，但他的背包最多只能装 $W$ 个球。普通的背包问题无法满足 Cake，因此他想给这些球加上一些魔法。具体来说，如果他从第 $i$ 种球中各取了 $k_i$ 个，那么该方案的代价为 $C = k_1^{c_1} k_2^{c_2} \dots k_n^{c_n}$。我们想知道，对于所有最多拿走 $W$ 个球的可能方案，所有方案的总代价之和模 998244353 的值是多少。

输入格式

第一行包含两个整数 $n$ 和 $W$。

第二行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$，两两之间用空格隔开。

输出格式

输出总代价模 998244353 的值。

数据范围

保证 $n \le 10^5$，$W \le 10^{18}$，且 $\sum c_i \le 10^5$。

样例

输入样例 1

4 5
1 2 3 4

输出样例 1

31

说明

对于样例输入，代价非零的方案 $(k_1, k_2, k_3, k_4)$ 共有：$(1, 1, 1, 2)$、$(1, 1, 2, 1)$、$(1, 2, 1, 1)$、$(2, 1, 1, 1)$ 和 $(1, 1, 1, 1)$。总代价为 $2^4 + 2^3 + 2^2 + 2^1 + 1 = 31$。