問題文

すぬけくんは誕生日に 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
• 入力はすべて整数

入力例 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