F - Hop Sugoroku Editorial /

Time Limit: 2.5 sec / Memory Limit: 1024 MB

配点 : 525 点

問題文

一列に並んだ N 個のマス 1,2,\dots,N と長さ N の数列 A=(A_1,A_2,\dots,A_N) があります。
最初、マス 1 は黒く、他の N-1 個のマスは白く塗られており、 1 つのコマがマス 1 に置かれています。

以下の操作を 0 回以上好きな回数繰り返します。

  • コマがマス i にあるとき、ある正整数 x を決めてコマをマス i + A_i \times x に移動させる。
    • 但し、 i + A_i \times x > N となるような移動はできません。
  • その後、マス i + A_i \times x を黒く塗る。

操作を終えた時点で黒く塗られたマスの集合として考えられるものの数を 998244353 で割った余りを求めてください。

制約

  • 入力は全て整数
  • 1 \le N \le 2 \times 10^5
  • 1 \le A_i \le 2 \times 10^5

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 \dots A_N

出力

答えを整数として出力せよ。

入力例 1

5
1 2 3 1 1

出力例 1

8

黒く塗られたマスの集合として考えられるものは以下の 8 通りです。

  • マス 1
  • マス 1,2
  • マス 1,2,4
  • マス 1,2,4,5
  • マス 1,3
  • マス 1,4
  • マス 1,4,5
  • マス 1,5

入力例 2

1
200000

出力例 2

1

入力例 3

40
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

出力例 3

721419738

998244353 で割った余りを求めることに注意してください。

Score : 525 points

Problem Statement

There is a row of N squares labeled 1,2,\dots,N and a sequence A=(A_1,A_2,\dots,A_N) of length N.
Initially, square 1 is painted black, the other N-1 squares are painted white, and a piece is placed on square 1.

You may repeat the following operation any number of times, possibly zero:

  • When the piece is on square i, choose a positive integer x and move the piece to square i + A_i \times x.
    • Here, you cannot make a move with i + A_i \times x > N.
  • Then, paint the square i + A_i \times x black.

Find the number of possible sets of squares that can be painted black at the end of the operations, modulo 998244353.

Constraints

  • All input values are integers.
  • 1 \le N \le 2 \times 10^5
  • 1 \le A_i \le 2 \times 10^5

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_N

Output

Print the answer as an integer.

Sample Input 1

5
1 2 3 1 1

Sample Output 1

8

There are eight possible sets of squares painted black:

  • Square 1
  • Squares 1,2
  • Squares 1,2,4
  • Squares 1,2,4,5
  • Squares 1,3
  • Squares 1,4
  • Squares 1,4,5
  • Squares 1,5

Sample Input 2

1
200000

Sample Output 2

1

Sample Input 3

40
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Sample Output 3

721419738

Be sure to find the number modulo 998244353.