103355: [Atcoder]ABC335 F - Hop Sugoroku

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$.

问题描述

有一排标号为$1,2,\dots,N$的方格和一个长度为$N$的序列$A=(A_1,A_2,\dots,A_N)$。

最初，方格$1$被涂成黑色，其他$N-1$个方格被涂成白色，且在方格$1$上放置了一个棋子。

你可以重复执行任意多次（包括零次）以下操作：

• 当棋子在方格$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

有八种可能的方格被涂成黑色的集合：

• 方格$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$取模。