AT_ajo2025_final_b Interpolation

すぬけくん在生日那天收到了两个 $N$ 次整系数多项式 $f(x), g(x)$。すぬけくん非常高兴，他定义 $h(x)=2^x \times f(x) + g(x)$，并计算了 $h(0), h(1), \cdots, h(2N+1)$ 的值（对 $998244353$ 取模）。然后他将 $h(i) \bmod 998244353 = A_i$ 记了下来。 有一天，すぬけくん不小心把 $f(x), g(x)$ 弄丢了，只剩下 $A_0, A_1, \cdots, A_{2N+1}$ 的值。不过，すぬけくん很聪明，他意识到在本题的限制条件下（他甚至知道自己是题目中的角色！），可以唯一恢复 $f(x), g(x)$ 的系数（对 $998244353$ 取模）。 现在给定 $A_0, A_1, \cdots, A_{2N+1}$ 以及 $X$，请你计算 $h(X) \bmod 998244353$ 的值。

输入通过标准输入按以下格式给出。 > $N$ $X$ $A_0$ $A_1$ $\ldots$ $A_{2N+1}$

请输出答案。

### 样例说明 1 $f(x)=2,\,g(x)=3$。 ### 样例说明 2 $f(x)=2x+1,\,g(x)=x+2$。 ### 数据范围 - $0 \leq N \leq 125000$ - $0 \leq X \leq 9 \times 10^8$ - $0 \leq A_i < 998244353$ - 所有输入均为整数。 由 ChatGPT 5 翻译