Contest Duration: - (local time) (100 minutes) Back to Home
F - Predilection /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 制約

• 1 \leq N \leq 2\times 10^5
• |A_i| \leq 10^9
• 入力はすべて整数

### 入力

N
A_1 A_2 \cdots A_N


### 入力例 1

3
1 -1 1


### 出力例 1

4


0 回以上の操作の後の数列として考えられるのは以下の 4 通りです。

• {1,-1,1}
• {1,0}
• {0,1}
• {1}

### 入力例 2

10
377914575 -275478149 0 -444175904 719654053 -254224494 -123690081 377914575 -254224494 -21253655


### 出力例 2

321


Score : 500 points

### Problem Statement

Given is a sequence A of length N. You can do this operation any number of times: when the length of the sequence is at least 2, choose two adjacent values, delete them, and insert their sum where they were. How many sequences can result from zero or more operations? Find the count modulo 998244353.

### Constraints

• 1 \leq N \leq 2\times 10^5
• |A_i| \leq 10^9
• All values in input are integers.

### Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N


### Sample Input 1

3
1 -1 1


### Sample Output 1

4


The following four sequences can result from zero or more operations.

• {1,-1,1}
• {1,0}
• {0,1}
• {1}

### Sample Input 2

10
377914575 -275478149 0 -444175904 719654053 -254224494 -123690081 377914575 -254224494 -21253655


### Sample Output 2

321