Coin 1

Interview

Time limit0.5sMemory limit4 MB

Summary

Given n coin denominations, count the number of combinations (order irrelevant, unlimited supply) that sum exactly to k.

Level: Medium4 of 10
Topics: Dynamic programming
Solved: No attempts yet

Problem

There are n kinds of coins, each with its own value. You may use any number of coins of each kind. Count how many combinations of these coins have total value exactly k.

If the number of coins used from each kind is the same, different orders of the coins are counted as the same combination.

Input

The first line contains the number of coin kinds n and the target amount k. (1 <= n <= 100, 1 <= k <= 10,000)

Each of the next n lines contains one coin value. Every value is a positive integer at most 100,000.

Output

Print the number of ways to make total value k on the first line. The answer is less than 2^31.

Examples1

Example 1
Input
```
3 10
1
2
5
```
Expected output
```
10
```