[PumpkinOI Round 1] 递推

>一个简单的问题，什么是递推？

定义一个数列 $\{a_0 \dots a_{n - 1} \}$ 的递推式为满足下式的序列 $\{r_0\dots r_m\}$： $$\sum_{j = 0} ^ m r_j a_{i - j} = 0, \forall i \ge m$$ $m$ 称为该递推式的阶数。特别地，$r_0\neq 0$。 给你一个无限长的数列 $\{a_i\}$ 的前 $n$ 项以及数列 $\{a_i\}$ 的一个阶数为 $n$ 的递推式 $\{b_i\}$。 要求求出数列 $\{a_i\}$ 的所有项之和。答案对 $998244353$ 取模。 可以证明，对于任意一个模 $998244353$ 意义下输入，都存在实数意义下的一个对应数列的答案是收敛的。

第一行一个正整数 $n$。 第二行输入 $n$ 个整数，表示序列 $\{a_i\}$ 的前 $n$ 项即 $\{a_0 \dots a_{n-1}\}$ 在模 $998244353$ 意义下的值。 第三行输入 $n+1$ 个整数，表示递推式 $\{b_0\dots b_n\}$ 在模 $998244353$ 意义下的值。

输出一行一个整数，表示数列 $\{a_i\}$ 的所有项之和对 $998244353$ 取模的结果。 保证答案可以在模 $998244353$ 意义下表示，即如果最终的答案为分数 $\frac qp$（可以证明答案肯定是一个有理数），保证 $p\not\equiv0\pmod {998244353}$。

1
1
1 499122176

2

2
1 1
1 199648870 99824435

14

1
1
1 499122177

665496236

**样例解释 #1** $499122176\equiv -\frac12\pmod {998244353}$。 $\forall i\ge n,a_i-\frac12\times a_{i-1}=0$ 即 $a_i=\frac12\times a_{i-1}$，即数列 $\{a_i\}$ 是等比数列 $1,\frac12,\frac14,\dots$。其和收敛于 $2$。 **样例解释 #2** $199648870\equiv -0.6\pmod {998244353},99824435\equiv -0.3\pmod {998244353}$。 $\forall i\ge n,a_i-0.6\times a_{i-1}-0.3\times a_{i-2}=0$ 即 $a_i=0.6\times a_{i-1}+0.3\times a_{i-2}$。经计算，其和收敛于 $14$。 **本题使用子任务捆绑/依赖** 对于所有子任务，$1\le n\le5\times 10^3$， $0\le a_i,b_i< 998244353$。特别地，$b_0\neq 0$。 | 子任务编号 | 分值 | $n\le$ | 依赖 | | :-----------: | :-----------: | :-----------: | :-----------: | | $1$ | $30$ | $1$ | 无 | | $2$ | $30$ | $2$ | $1$ | | $3$ | $40$ | $5\times 10^3$ | $1,2$ |