#215922. 【MX-X26-T6】「Cfz Round 7」vivi

こんな話など　忘れておくれ　/　这样的话之类的　就请你忘掉吧

言いたいことは　一つもないさ　/　想说出口的事　一件也没有了

商店里有 条「鱼鱼」排成一排，第 条「鱼鱼」的体积为 。

Yuki 有一个体积为 的背包，她打算从 到 依次考虑每条「鱼鱼」：如果当前「鱼鱼」的体积小于等于背包剩余体积，则将该「鱼鱼」装入背包，否则不将该「鱼鱼」装入背包。当一条体积为 的「鱼鱼」被装入背包时，背包的剩余体积会减少 。

由于 Yuki 是魔法少女，她可以让背包的 初始体积 为任意非负整数，不过她不会在考虑「鱼鱼」的过程中修改背包的体积。

设 表示第 条「鱼鱼」的选取状态；具体地，若第 条「鱼鱼」被装入背包了则 ，否则 。你需要求出，上述策略可以生成多少种序列 。

第一行包含一个整数 ，表示该测试点所属的子任务编号。样例满足 。

第二行包含一个整数 。

第三行包含 个整数 。

输出一行，包含一个非负整数，表示可以生成的不同的序列 的数量。

样例输入 1

0
3
1 3 8

样例输出 1

4

样例输入 2

0
4
1 3 1 4

样例输出 2

6

样例输入 3

0
5
16 8 4 2 1

样例输出 3

32

样例输入 4

0
6
7 4 4 6 8 7

样例输出 4

9

样例 1 解释

• 当背包的初始体积 时，；
• 当背包的初始体积 时，；
• 当背包的初始体积 时，；
• 当背包的初始体积 时，。

容易证明，当背包的初始体积 等于其他非负整数时，生成的 一定为这 种中的 种，因此答案为 。

样例 2 解释

• 当背包的初始体积 时，；
• 当背包的初始体积 时，；
• 当背包的初始体积 时，；
• 当背包的初始体积 时，；
• 当背包的初始体积 时，；
• 当背包的初始体积 时，；

容易证明，当背包的初始体积 等于其他非负整数时，生成的 一定为这 种中的 种，因此答案为 。

数据范围

对于所有测试数据，均有：

• ；
• 对于所有 ，均有 。

本题采用捆绑测试。

• Subtask 1（7 points）：。
• Subtask 2（11 points）：；对于所有 ，均有 。
• Subtask 3（8 points）：；对于所有 ，均有 。
• Subtask 4（5 points）：。
• Subtask 5（12 points）：；对于所有 ，均有 ；
• Subtask 6（15 points）：。
• Subtask 7（13 points）：。
• Subtask 8（12 points）：保证序列 单调不增。
• Subtask 9（17 points）：无特殊限制。