分数: 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).