时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
瓜瓜在设计游戏关卡。游戏共有
关，只能顺次尝试。第
关有
种通关方法，每过一关就可以得到一个徽章；或者选择放弃，跳到下一关但没有徽章。
如果完全通关两个玩家存在一关通过方法不同，那么称他们有不同的游戏路径。
现在瓜瓜设计好了
的值，他想知道分别获得
)
个徽章时，所有可能的游戏路径有多少条。
因为答案可能很大，请对
取模。
输入描述:
第一行有两个整数 
，其中 
。
第二行有 个整数，分别为 
，其中 
。
输出描述:
在一行输出 
个整数，分别表示得到 
个徽章时，可能的路径条数。