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

【题目描述】

阿基米德需要把传送带上的 $n$ 个零件箱依次装上若干辆运输车．第 $j$ 辆车有 $j$ 个相同的储物舱，因此装上这辆车的零件总重量必须能够被 $j$ 平均分配．

传送带上依次排列着 $n$ 个零件箱，第 $i$ 个零件箱的重量为 $a_i$．你需要把所有零件箱装车，装车时不能改变它们的顺序，每辆车必须装走一段非空且连续的零件箱．

设一种装车方案一共使用了 $k$ 辆车，并按照装车顺序将它们编号为 $1,2,\ldots,k$．如果对于每一个 $1\le j\le k$，第 $j$ 辆车所装零件箱的总重量都是 $j$ 的倍数，那么称这种装车方案是合法的．

请计算合法装车方案的数量．由于答案可能很大，你只需要输出它对 $998244353$ 取模后的结果．

两种方案只要存在两个相邻零件箱在其中一种方案中被装上同一辆车、而在另一种方案中被装上不同车辆，就被视为不同的装车方案．

【输入描述】

第一行输入一个整数 $n$，表示零件箱数量．

第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$，其中 $a_i$ 表示第 $i$ 个零件箱的重量．

【输出描述】

输出一个整数，表示合法装车方案的数量对 $998244353$ 取模后的结果．

样例 1

输入

3
1 1 1

输出

2

解释

共有两种合法装车方案：

• 将三个零件箱全部装上第 $1$ 辆车；
• 将第一个零件箱装上第 $1$ 辆车，将后两个零件箱装上第 $2$ 辆车，两辆车的载重分别为 $1$ 和 $2$．

先装前两个零件箱、再装最后一个零件箱的方案不合法，因为第 $2$ 辆车的载重为 $1$，不能被 $2$ 整除．

样例 2

输入

4
0 0 0 0

输出

8

解释

任意一辆车的载重都是 $0$，因此三个相邻零件箱之间都可以独立选择是否换车，共有 $2^3=8$ 种合法方案．

样例 3

见选手目录下的 Data/sample3.in 和 Data/sample3.ans．

该样例满足子任务 $1$ 的限制：$n\le18$．

样例 4

见选手目录下的 Data/sample4.in 和 Data/sample4.ans．

该样例满足子任务 $2$ 的限制：$n\le120$．

样例 5

见选手目录下的 Data/sample5.in 和 Data/sample5.ans．

该样例满足子任务 $3$ 的限制：$n\le450$．

样例 6

见选手目录下的 Data/sample6.in 和 Data/sample6.ans．

该样例满足子任务 $4$ 的特殊性质：对所有 $1\le i\le n$，均有 $a_i=0$．

样例 7

见选手目录下的 Data/sample7.in 和 Data/sample7.ans．

该样例满足子任务 $5$ 的特殊性质：对所有 $1\le i\le n$，均有 $a_i=1$．

样例 8

见选手目录下的 Data/sample8.in 和 Data/sample8.ans．

该样例对应子任务 $6$，满足完整数据范围，无特殊性质．

【数据规模与约定】

对于所有测试数据，保证：

• $1\le n\le5000$；
• $0\le a_i\le10^9$．

【大样例下载链接】

点击下载本题选手目录