F - Predilection Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

長さ N の数列 A が与えられます。 数列の長さが 2 以上のとき、隣接する二つの値を選び、それらを削除し、それらが元にあった位置にそれらの和を挿入するという操作を好きなだけ行えます。 0 回以上の操作の後の数列として考えられるものは何通りあるか求め、998244353 で割ったあまりを出力してください。

制約

  • 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

Output

Print the answer.

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