← 返回题目列表

AtCoder · ttpc2022_m

M. 许多产品

中文机器翻译题面 查看原题

配点 : 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