Many Products
题目描述
给定两个正整数 N,M,以及整数序列 A=(A1,A2,…,AN)。
设 X 为所有满足
i=1∏Nxi=M
的正整数元组 (x1,x2,…,xN) 组成的集合。
请计算
$$\sum_{(x_1,\ldots,x_N)\in\mathcal X}
\prod_{i=1}^{N}(x_i+A_i)$$
对 998244353 取模的结果。
输入格式
N M
A_1 A_2 ... A_N
输入仅包含一组数据,所有数均为整数。
输出格式
输出一个整数,表示所求结果对 998244353 取模的值。
数据范围
- 1≤N≤2×105。
- 1≤M≤1012。
- 0≤Ai<998244353。
样例输入 1
2 3
0 1
样例输出 1
10
样例说明 1
X={(1,3),(3,1)},所以答案为
(1+0)(3+1)+(3+0)(1+1)=10.
样例输入 2
5 1
0 1 2 3 4
样例输出 2
120
样例输入 3
10 314159265358
0 1 2 3 4 5 6 7 8 9
样例输出 3
658270849