C - Shopping Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君は、スーパーマーケットで買い物をしています。

このスーパーマーケットには N 個の商品が並んでおり、各商品には 1 から N までの番号が付けられています。商品 i の価格は P_i 円です。なお、異なる番号の商品であっても、価格が同じであることがあります。

高橋君は、これらの商品の中から 1 個以上を選んで購入し、購入した商品の価格の合計がちょうど K 円になるようにしたいと考えています。ただし、各商品は最大 1 個しか購入できません。

購入する商品の番号の集合が異なるものを異なる方法として数えるとき、ちょうど K 円分の商品を購入する方法の数を 10^9 + 7 で割った余りを求めてください。例えば、価格が同じ商品が複数ある場合でも、選んだ商品の番号の集合が異なれば、それらは異なる方法として数えます。

制約

  • 1 \leq N \leq 100
  • 1 \leq K \leq 10000
  • 1 \leq P_i \leq K
  • 入力はすべて整数

入力

N K
P_1 P_2 \ldots P_N
  • 1 行目には、商品の個数を表す整数 N と、目標とする合計金額を表す整数 K が、スペース区切りで与えられる。
  • 2 行目には、各商品の価格を表す整数 P_1, P_2, \ldots, P_N が、スペース区切りで与えられる。

出力

ちょうど K 円分の商品を購入する方法の数を 10^9 + 7 で割った余りを 1 行で出力してください。なお、条件を満たす方法が存在しない場合は 0 を出力してください。

入力例 1

4 7
2 3 4 5

出力例 1

2

入力例 2

6 10
1 2 3 4 5 6

出力例 2

5

入力例 3

10 100
10 20 30 40 50 15 25 35 45 55

出力例 3

21

Score : 366 pts

Problem Statement

Takahashi is shopping at a supermarket.

There are N items available at this supermarket, each numbered from 1 to N. The price of item i is P_i yen. Note that different items may have the same price.

Takahashi wants to select and purchase 1 or more of these items such that the total price of the purchased items is exactly K yen. However, each item can be purchased at most once.

Counting two ways as different if the sets of item numbers purchased are different, find the number of ways to purchase items totaling exactly K yen, modulo 10^9 + 7. For example, even if multiple items have the same price, they are counted as different ways if the sets of selected item numbers differ.

Constraints

  • 1 \leq N \leq 100
  • 1 \leq K \leq 10000
  • 1 \leq P_i \leq K
  • All inputs are integers

Input

N K
P_1 P_2 \ldots P_N
  • The first line contains an integer N representing the number of items and an integer K representing the target total price, separated by a space.
  • The second line contains integers P_1, P_2, \ldots, P_N representing the price of each item, separated by spaces.

Output

Print in one line the number of ways to purchase items totaling exactly K yen, modulo 10^9 + 7. If there is no way to satisfy the condition, print 0.

Sample Input 1

4 7
2 3 4 5

Sample Output 1

2

Sample Input 2

6 10
1 2 3 4 5 6

Sample Output 2

5

Sample Input 3

10 100
10 20 30 40 50 15 25 35 45 55

Sample Output 3

21