← 返回题目列表

AtCoder · dwacon6th_prelims_e

E. 跨度覆盖

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

分数: 1100 点

问题陈述

Niwango 买了一块可以表示为半开区间的土地 [0, X).

Niwango 将布局 N 这片土地上的乙烯基片材。纸张已编号 1,2, \ldots, N,并且它们是可区分的。 对于片材 i,他可以选择一个整数 j 这样 0 \leq j \leq X - L_i 和封面 [j, j + L_i) 与此表。

找出用床单覆盖土地的方法数量,使得没有点 [0, X) 仍然未被覆盖,模数 (10^9+7)。 当且仅当存在一个整数时,我们考虑两种不同的覆盖土地的方法 i (1 \leq i \leq N) 使得工作表覆盖的区域 i 是不同的。

约束

  • 1 \leq N \leq 100
  • 1 \leq L_i \leq X \leq 500
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N X
L_1 L_2 \ldots L_N

输出

打印答案。


示例输入 1

3 3
1 1 2

示例输出 1

10
  • 如果我们忽略整个区间是否被覆盖,有 18 布置图纸的方法。
  • 其中,有 4 离开的方式 [0, 1) 未覆盖,并且 4 离开的方式 [2, 3) 未覆盖。
  • 其他每种方式都覆盖整个区间 [0,3),所以答案是 10.

示例输入 2

18 477
324 31 27 227 9 21 41 29 50 34 2 362 92 11 13 17 183 119

示例输出 2

134796357
  • 求模数的方法 (10^9+7).