08760. 义卖书市购书方案 · 林老师的题库

题目描述

学校举办爱心义卖活动，图书角拿出 $n$ 本旧书参加义卖书市，第 $i$ 本书的定价为 $a_{i}$ 元，每本书只有一本，每本书最多买一次。

社团发给你一张面值 $x$ 元的购书券，付款时必须把券里的钱恰好花完：所买书的总定价要恰好等于 $x$ 元，不能多也不能少。

你想知道有多少种不同的选购方案能把这张券恰好花完。两种方案不同，当且仅当存在某本书在一种方案里被买下，而在另一种方案里没有被买下。

第一行两个整数 $n, x$ ，分别表示书的本数与购书券面值。

第二行 $n$ 个正整数 $a_{1}, a_{2}, \dots, a_{n}$ ，用空格分隔，表示每本书的定价。

一行一个整数，表示总定价恰好为 $x$ 元的选购方案数对 $1 0^{9} + 7$ 取模的结果（方案数可能很大，只需输出余数）。可能没有任何方案，此时输出 $0$ 。

输入

4 6
1 2 3 3

输出

样例解释：三种方案：买第 $1, 2, 3$ 本（ $1 + 2 + 3 = 6$ ）；买第 $1, 2, 4$ 本（ $1 + 2 + 3 = 6$ ）；买第 $3, 4$ 本（ $3 + 3 = 6$ ）。

样例解释：任何子集的总定价都不等于 $5$ ，方案数为 $0$ 。

对于 $100%$ 的数据： $1 \leq n \leq 100$ ， $1 \leq x \leq 1 0^{4}$ ， $1 \leq a_{i} \leq 1000$ 。

本题共 $10$ 个测试点，每个测试点 $10$ 分。