配点 : 400 点
問題文
正整数 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)
入力
输入是按以下格式从标准输入给出的。
N M A_1 A_2 \dots A_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