#P18645. Many Products

Many Products

Many Products

题目描述

给定两个正整数 N,MN,M,以及整数序列 A=(A1,A2,…,AN)A=(A_1,A_2,\ldots,A_N)。

设 X\mathcal X 为所有满足

∏i=1Nxi=M\prod_{i=1}^{N}x_i=M

的正整数元组 (x1,x2,…,xN)(x_1,x_2,\ldots,x_N) 组成的集合。

请计算

$$\sum_{(x_1,\ldots,x_N)\in\mathcal X} \prod_{i=1}^{N}(x_i+A_i)$$

对 998244353998244353 取模的结果。

输入格式

N M
A_1 A_2 ... A_N

输入仅包含一组数据,所有数均为整数。

输出格式

输出一个整数,表示所求结果对 998244353998244353 取模的值。

数据范围

  • 1≤N≤2×1051\le N\le2\times10^5。
  • 1≤M≤10121\le M\le10^{12}。
  • 0≤Ai<9982443530\le A_i<998244353。

样例输入 1

2 3
0 1

样例输出 1

10

样例说明 1

X={(1,3),(3,1)}\mathcal X=\{(1,3),(3,1)\},所以答案为

(1+0)(3+1)+(3+0)(1+1)=10.(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