分数: 525 点
问题陈述
有一排 N 标记的方块 1,2,\dots,N 和一个序列 A=(A_1,A_2,\dots,A_N) 长度 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.