問題文

正整数 N, M が与えられます。N 個の正整数の組 (x_1,x_2,\dots ,x_N) であって \displaystyle\prod_{i=1}^{N}x_i=M を満たすものすべての集合を \bm{X} とします。

\displaystyle\sum_{(x_1,x_2,\dots ,x_N)\in \bm{X}}\prod_{i=1}^{N} (x_i+A_i) を 998244353 で割ったあまりを求めてください。

制約

• 入力はすべて整数
• 1\le N\le 2\times 10^5
• 1\le M\le 10^{12}
• 0\le A_i\lt 998244353 (1\le i\le N)

入力例 1

2 3
0 1

出力例 1

10

x_1\times x_2=3 を満たす正整数の組 (x_1,x_2) は (1,3),(3,1) の 2 組存在します。これらに対する \prod_{i=1}^{N} (x_i+A_i) の値はそれぞれ (1+0)\times (3+1)=4,(3+0)\times (1+1)=6 なので、これらの和である 10 が答えになります。

入力例 2

5 1
0 1 2 3 4

出力例 2

120

x_1=x_2=x_3=x_4=x_5=1 に対する \prod_{i=1}^{N} (x_i+A_i) の値は (1+0)\times (1+1)\times (1+2)\times (1+3)\times (1+4)=120 です。

入力例 3

10 314159265358
0 1 2 3 4 5 6 7 8 9

出力例 3

658270849