传统题 4000ms 256MiB

齿轮装配线

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

机械工坊里有一条长度为 WW 的装配轨道,仓库里有 nn 个齿轮,编号为 1,2,…,n1,2,\ldots,n。

第 ii 个齿轮安装到轨道上会占据恰好 wiw_i 个单位长度。每个齿轮至多安装一次,也可以不安装。

设选中齿轮的编号集合为 S⊆{1,2,…,n}S\subseteq\{1,2,\ldots,n\}。当且仅当

∑i∈Swi=W\sum_{i\in S}w_i=W

时,选中的齿轮恰好完整铺满整条轨道。

每个齿轮都按编号区分。两种选法不同,当且仅当它们对应的编号集合 SS 不同;即使 wi=wjw_i=w_j,选择齿轮 ii 与选择齿轮 jj 也视为不同方案。

请计算满足条件的集合 SS 的数量,并对

109+710^9+7

取模。如果不存在合法选法,答案为 00。

输入格式

第一行输入两个整数 n,Wn,W(1≤n≤1001\le n\le 100,1≤W≤1041\le W\le 10^4),分别表示齿轮数量和轨道长度。

第二行输入 nn 个整数 w1,w2,…,wnw_1, w_2, \dots, w_n(1≤wi≤1041\le w_i\le 10^4),表示每个齿轮占用的单位长度。

输出格式

输出一行一个整数,表示满足

∑i∈Swi=W\sum_{i\in S}w_i=W

的编号集合 SS 的数量对 109+710^9+7 取模后的结果。

样例

5 5
1 2 3 2 5
4
3 7
2 2 4
0

提示

样例 11 中,占用长度之和恰好为 55 的编号集合有

$$\{2,3\},\quad \{3,4\},\quad \{1,2,4\},\quad \{5\},$$

共 44 种。注意,齿轮 22 与齿轮 44 的占用长度都是 22,但它们按编号区分,因此 {2,3}\{2,3\} 与 {3,4}\{3,4\} 是两种不同的选法。

样例 22 中,任意选法的占用长度之和只可能是 0,2,4,6,80,2,4,6,8,不存在恰好等于 77 的选法,因此答案为 00。

下载正式赛最终版 PDF 题面