問題文
高桥对自己的头脑不自信,但对自己的身体有信心。于是高桥决定参加健美比赛。
高桥有肌肉。 包括 N 件。 高桥君,直到健美比赛举行。 D 我决定每天训练几天。
高桥每天选择一块肌肉并进行训练。 1增加公斤。
高桥设定了一个目标,即他应该增加每块肌肉多少才能赢得健美比赛。然而,我不知道我应该遵循什么样的训练计划来实现这个目标。
高桥君有多少种不同的训练计划? 使用 1000000007找到它。
入力
输入是按以下格式从标准输入给出的。
N D a_1 a_2 ... a_N
- 1 行是高桥的肌肉数量。 N (1 \leq N \leq 30)和培训日 D (1 \leq D \leq 10^9) 用空格分隔。 在
- 2 从行 N+1 行到 N 行是i (1 \leq i \leq N) 您想要增加肌肉质量的最小公斤数的目标 如果您正确回答 a_i\ (1 \leq a_i \leq 30) 。 表示
部分点
- N \leq 5,\ a_i \leq 5,\ D \leq 500 的输入正确时,280 作为满分的部分分数,40 点。 如果您正确回答了所有满足
- N \leq 5,\ a_i \leq 5 的输入正确时,280 与上述分开,作为满分的部分分数。 如果您正确回答 100 点。 如果您正确回答了所有满足
出力
高桥可以通过多少种方式制定时间表来实现他的所有目标? 打印除以1000000007 输出除以后的余数。
另外,在输出末尾放置一个换行符。
入力例 1
2 3 1 1
出力例 1
6
训练肌肉2没有3训练了几天。
时间表从第一天开始按顺序设置:{1,1,2}、{1,2,1}、{1,2,2}、{2,1,1}、{2,1,2}、{2,2,1}。6是的。 请注意,我们正在寻找除以
入力例 2
4 4 1 1 1 1
出力例 2
24
训练肌肉4没有4每天的训练1你需要选择一块肌肉,其组合是4!=24是的。 请注意,我们正在寻找除以
入力例 3
13 12345678 1 2 3 4 5 6 7 8 9 10 11 12 13
出力例 3
910759485