配点 : 800 点
問題文
小助君在生日时收到了 N 次整数係数多項式 f(x),g(x) 。 对此感到高兴的小助君,h(x)=2^x\times f(x) + g(x) 定义了,h(0),h(1),\cdots,h(2N+1) 的值用 \text{mod }{998244353} 进行了计算。 然后,h(i) \bmod 998244353=A_i 并记录下它是
有一天,小助君不小心弄丢了 f(x),g(x) 。 现在只剩下 A_0,A_1,\cdots,A_{2N+1} 的值了。 不过小助君很聪明,所以即使在否定这个问题的情况下(小助君知道连“自己”都是题面中的登场人物!),也能从这些值中求出 f(x),g(x) 的系数 \text{mod }{998244353} 发现可以唯一恢复。
A_0,A_1,\cdots,A_{2N+1} 以及 X 由于给出了,h(X) \bmod 998244353 请计算的值。
制約
- 0 \leq N \leq 125000
- 0 \leq X \leq 9 \times 10^8
- 0 \leq A_i < 998244353
- 所有输入均为整数
入力
输入将按照以下格式从标准输入给出。
N X
A_0 A_1 \ldots A_{2N+1}
出力
输出答案。
入力例 1
0 2 5 7
出力例 1
11
f(x)=2,g(x)=3 是。
入力例 2
1 5 3 9 24 61
出力例 2
359
f(x)=2x+1,g(x)=x+2 是。
入力例 3
3 0 785439575 250040585 709423541 945005786 19237225 404191279 250876592 22672563
出力例 3
785439575
入力例 4
10 12345678 519729086 344065186 273714212 560047125 139793596 542901248 520999410 855572558 498896932 418633758 742973826 248730678 238856535 319502970 908902333 164543594 245101681 197971506 714635866 966125570 768080799 80565655
出力例 4
57546937