#C. 小木棍

    传统题 1000ms 256MiB

小木棍

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

乔治有一根小木棍,他把这根木棍随意砍成更小的木棍,直到每段的长都不超过一定值,在经过这一流程后,他得到了 nn 段短木棍,第 ii 段短木棍的长度是 AiA_i

但小凯过来了,他本来是想拿这根小木棍去玩游戏的,现在小凯很生气,因此小凯向乔治提出了一个问题。

小凯把这些短木棍按照一定顺序排列后,他需要乔治把这些短木棍按照这个顺序来划分成若干个非空连续子序列。并且还需要满足如下要求:

  • 若一共分成了 kk 段,那么对于每一段连续子序列,若其为第 ii 段,那么这段内的短木棍总长要是 ii 的倍数。

小凯想让乔治回答有多少种划分方式能够满足如上需求。

乔治很苦恼,因此他需要你的帮助来解决这个问题。

Format

Input

第一行一个正整数 NN ,表示一共有 NN 个短木棍。

第二行共 NN 个正整数 AiA_i ,表示第 ii 段短木棍的长度。.

Output

输出划分方案数对 998244353 取模的值。

Samples

4
1 2 3 4
3
5
8 6 3 3 3
5

样例解释

对于第一组样例,有如下划分方法:

[ 1 | 2 | 3 | 4 ]
[1 2 3 4]
[1 2 3 | 4]

对于第二组样例,有如下划分方法:

[8 6 3 3 3]
[8 | 6 | 3 3 3]
[8 6 | 3 3 | 3]
[8 | 6 3 3 | 3]
[8 6 3 | 3 3]

Limitation

  • 对于 40% 的数据,1n2001\leq n \leq 200
  • 对于 100% 的数据,1n2000,1Ai1091\leq n \leq 2000, 1\leq A_i \leq 10^9

7.17日冲刺班测试

未参加
状态
已结束
规则
OI
题目
4
开始于
2024-7-17 14:20
结束于
2024-7-17 17:20
持续时间
3 小时
主持人
参赛人数
28