乔治有一根小木棍,他把这根木棍随意砍成更小的木棍,直到每段的长都不超过一定值,在经过这一流程后,他得到了 n 段短木棍,第 i 段短木棍的长度是 A_i 。
但小凯过来了,他本来是想拿这根小木棍去玩游戏的,现在小凯很生气,因此小凯向乔治提出了一个问题。
小凯把这些短木棍按照一定顺序排列后,他需要乔治把这些短木棍按照这个顺序来划分成若干个非空连续子序列。并且还需要满足如下要求:
若一共分成了 i 段,那么对于每一段连续子序列,若其为第 i 段,那么这段内的短木棍总长要是 i 的倍数。
小凯想让乔治回答有多少种划分方式能够满足如上需求。
乔治很苦恼,因此他需要你的帮助来解决这个问题。
第一行一个正整数 N ,表示一共有 N 个短木棍。
第二行共 N 个正整数 A_i,表示第 i 段短木棍的长度。
输出划分方案数对 998244353 取模的值。
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]
数据说明:
对于 40% 的数据,1
对于 100% 的数据,1 \leq n \leq 2000,1 \leq A_i \leq 10^9