Number of ways to make an amount with coins — interview question

A bus conductor accepts coins of n distinct values, with an unlimited supply of each. In how many different ways can a fare of T be paid exactly? Two ways are the same if they use the same number of each coin (order does not matter).

Print the count modulo 1 000 000 007.

Constraints

1 ≤ n ≤ 100
0 ≤ T ≤ 100000
1 ≤ coin ≤ 100000

Input and output

Input: Line 1: n and T. Line 2: the n coin values.
Output: One integer.

Examples

Input 1

3 5
1 2 5

Output

Four ways: 5; 2+2+1; 2+1+1+1; 1+1+1+1+1.

Input 2

1 3
2

Output

Only 2-rupee coins cannot make 3, so 0 ways.

Show hints

Let ways[x] be the number of ways to make x using the coins seen so far.
Loop over coins on the outside so each combination is counted once, not once per ordering.

Show the explanation

Use a 1-D table ways[0..T] with ways[0] = 1 (one way to pay nothing). For each coin c, sweep x from c up to T and add ways[x − c] to ways[x]. Because coins are the outer loop, every combination is built in one fixed coin order, so 1+2 and 2+1 are counted once. Swapping the loops would count ordered sequences instead — a common interview trap.

Original UniCircle question. Last reviewed 22 Oct 2026.