Infinite Sequence Sum with Recurrence

Given the first n terms of an infinite sequence \(\{a_i\}\) and a recurrence relation of order \(n\) with coefficients \(\{b_0, b_1, \dots, b_n\}\) (with \(b_0 \neq 0\)) satisfying

[ \sum_{j=0}^{n} b_j, a_{i-j} = 0 \quad \text{for all } i \ge n, ]

compute the sum of all terms of the sequence, i.e.,

[ S = \sum_{i\ge0}a_i, ]

and output (S) modulo (998244353).

You may assume that the real-valued series is convergent and that \(\sum_{j=0}^n b_j \not\equiv 0 \pmod{998244353}\) so that the answer exists modulo \(998244353\).

inputFormat

The input consists of three lines:

• The first line contains an integer \(n\) (\(1 \le n \le 10^5\)), the number of initial terms of the sequence.
• The second line contains \(n\) space-separated integers \(a_0, a_1, \dots, a_{n-1}\), representing the first \(n\) terms of the sequence.
• The third line contains \(n+1\) space-separated integers \(b_0, b_1, \dots, b_n\) (with \(b_0 \neq 0\)), representing the recurrence coefficients.

It is guaranteed that the series sum \(S\) converges in the real sense and \(\sum_{j=0}^n b_j \not\equiv 0 \pmod{998244353}\).

outputFormat

Output a single integer, the sum \(S = \sum_{i \ge 0}a_i\) modulo \(998244353\).

sample

1
5
2 3

2