← 返回题目列表

AtCoder · tenka1_2013_final_d

D. 天下一健美大赛

中文机器翻译题面 查看原题

問題文

高桥对自己的头脑不自信,但对自己的身体有信心。于是高桥决定参加健美比赛。

高桥有肌肉。 包括 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