Background

A simple question: what is a recurrence?

Problem Description

Define a recurrence of a sequence $\{a_0 \dots a_{n - 1}\}$ as a sequence $\{r_0\dots r_m\}$ that satisfies:

$$\sum_{j = 0} ^ m r_j a_{i - j} = 0, \forall i \ge m$$

$m$ is called the order of this recurrence. In particular, $r_0\neq 0$.

You are given the first $n$ terms of an infinite sequence $\{a_i\}$ and a recurrence $\{b_i\}$ of order $n$ for the sequence $\{a_i\}$.

Find the sum of all terms of the sequence $\{a_i\}$. Output the answer modulo $998244353$.

It can be proven that, for any input under modulo $998244353$, there exists a corresponding sequence in the real-number sense whose sum is convergent.

Input Format

The first line contains a positive integer $n$.

The second line contains $n$ integers, representing the first $n$ terms of the sequence $\{a_i\}$, i.e. $\{a_0 \dots a_{n-1}\}$, under modulo $998244353$.

The third line contains $n+1$ integers, representing the recurrence $\{b_0\dots b_n\}$ under modulo $998244353$.

Output Format

Output one integer on one line, representing the sum of all terms of the sequence $\{a_i\}$ modulo $998244353$.

It is guaranteed that the answer can be represented under modulo $998244353$. That is, if the final answer is a fraction $\frac qp$ (it can be proven that the answer must be a rational number), then $p\not\equiv0\pmod {998244353}$ is guaranteed.

1
1
1 499122176

2

2
1 1
1 199648870 99824435

14

1
1
1 499122177

665496236

Hint

Sample Explanation #1

$499122176\equiv -\frac12\pmod {998244353}$.

$\forall i\ge n,a_i-\frac12\times a_{i-1}=0$, i.e. $a_i=\frac12\times a_{i-1}$. So the sequence $\{a_i\}$ is a geometric sequence $1,\frac12,\frac14,\dots$, and its sum converges to $2$.

Sample Explanation #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$, i.e. $a_i=0.6\times a_{i-1}+0.3\times a_{i-2}$. After calculation, its sum converges to $14$.

This problem uses bundled/dependent subtasks.

For all subtasks, $1\le n\le5\times 10^3$, $0\le a_i,b_i< 998244353$. In particular, $b_0\neq 0$.

Subtask ID	Score	$n\le$	Depends On
$1$	$30$	$1$	None
$2$		$2$	$1$
$3$	$40$	$5\times 10^3$	$1,2$

Translated by ChatGPT 5