No.2754 Cumulate and Drop
Problem Statement
For a sequence $(a_1,a_2,\ldots,a_n)$, we call the sequence $(b_1,b_2,\ldots,b_n)$ defined by $b_i=a_1+\cdots+a_i$ its cumulative sum.
You are given a sequence $A=(A_1,A_2,\ldots,A_N)$ of length $N$. Repeat the following operation until the length of the sequence becomes $1$.
- Replace the sequence $A$ with its cumulative sum. Then, discard the first term of the sequence $A$.
When the length of the sequence becomes $1$, find the remainder when its term is divided by $998244353$.
Constraints
- $1\le N\le 2\times 10^5$
- $0\le A_i< 998244353$
- All input values are integers.
Input
$N$ $A_1$ $A_2$ $\cdots$ $A_N$
Output
Print a newline at the end.
Sample
Sample 1
Input
3 1 0 2
Output
4
Initially, the sequence is $(1,0,2)$. Taking the cumulative sum and discarding the first term gives $(1,3)$. Taking the cumulative sum and discarding the first term again gives $(4)$. Print $4$.
Sample 2
Input
9 3 1 4 1 5 9 2 6 5
Output
12784
Sample 3
Input
2 900000000 800000000
Output
701755647
Print the remainder when divided by $998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。