黑板写数-Hard
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
Background
Special for beginners, ^_^
Description
黑板上写有 个非负整数，第 个数为 。
你需要恰好进行 次如下操作：
- 从黑板上的非负整数中选出 个或多个，组成多重集 ，然后将 写到黑板上 次。
请你求出，经过 次操作后，黑板上可能出现的 个非负整数有多少种可能的方案数，结果对 取模。
Format
Input
第一行两个不超过 的正整数 和 ，分别表示黑板上初始的数的个数和操作次数。
第二行 个不超过 的正整数，表示黑板上初始的数。
Output
请输出答案。
Samples
6 3
1 1 4 5 1 4
7
Limitation
1s, 1024KiB for each test case.
