#214648. [CSP-X 2025 河南] 我要飞得更高 / rocket

2025 年河南省青少年程序设计能力认证 第二轮认证（小学组） 第四题

PDF 首页注意事项：输入文件中可能存在行末空格，请选手使用更完善的读入方式（例如 scanf 函数）避免出错。

你是一只毛毛虫，想要飞离地球前往空间站。

空间站位于距离地球 千米的位置，在 的每整数千米位置都有一个休息站。你最开始在地球上，距离地球 千米。为了飞到空间站，你准备了 种火箭，其中 号火箭能够前进 千米。为了顺利到达空间站，有如下的限制条件：

1. 每种火箭可以重复使用，且没有使用顺序的限制。
2. 每次前进后，如果无法到达空间站，你需要到达距离地球整数千米的位置的休息站，在休息站修整后重新使用某种火箭，直到到达空间站。
3. 宇宙很大，一旦和地球的距离超出了 千米就会失联，迷失在宇宙中，因此要避免这种情况。

出发前，你想算算顺利到达空间站有几种方案，因为方案数可能很多，你只需要输出方案数对 取模的结果。前进次数不同或前进次数相同但是存在某一步前进距离不同，则认为两个方案不同。

第一行两个空格隔开的正整数表示 和 。

接下来 行，第 行两个空格隔开的正整数 描述第 个火箭的能力。

输出一行一个非负整数表示方案数对 取模的结果。

样例输入 1

3 2
1 3
2 2

样例输出 1

4

样例输入 2

5 1
3 4

样例输出 2

0

【样例解释 #1】

第一个火箭可以让你前进 、 或 千米，第二个火箭可以让你前进 千米。

到达 千米位置的休息站的方案只有一个，就是从地球前进 千米。到达 千米位置的休息站的方案有两个，一个是前进 千米，一个是前进 千米再前进 千米。到达 千米的空间站的方案有四个，分别是前进 、前进 再前进 、前进 前进 、前进 前进 再前进 。

询问你到达 千米的空间站的方案数，所以输出 。

【样例解释 #2】

只有一种火箭，可以让你前进 或 千米。 到达 千米和 千米位置的休息站的方案都是 。无论怎么前进都只能停在中间或者距离超出 千米，无法顺利到达空间站，因此到达空间站的方案为 。

【测试点约束】

对于所有数据，，，。每个测试点的具体限制见下表：

::cute-table{tuack} | 测试点编号 | 约束 | | :--: | :--: | | | | | | | | | | | | 对于任意 ，保证 | | | 没有其他限制 |