Snuke 想要画一幅画。他的画仅仅是一个由黑白格子组成的序列。
最初，他准备了一张白纸，并将其分成了 $N$ 个格子。然后，他执行 $K$ 次操作。在第 $i$ 次操作中，他选择连续的 $a_i$ 个格子，并将这些格子涂成黑色。所有被选中的白色格子将变为黑色，而所有被选中的黑色格子将保持不变。
他总共能画出多少种不同的画？
请计算答案对 $10^9 + 7$ 取模的结果。如果两幅画中至少有一个格子的颜色不同，则认为它们是不同的。我们不旋转画作——例如，(黑-黑-白) 和 (白-黑-黑) 是不同的画。
10 2 1 1
55
在样例 1 中，你可以画出所有包含一个或两个黑色格子的画。
1000000000 4 2015 2015 123456789 27
782767239
The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.
This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.
If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.
Guidelines: