A turnstile is fed tokens one at a time until the running total reaches exactly the fare F. Tokens come in n distinct denominations with unlimited supply. Two payments are considered different if the sequence of token values inserted differs in any position (so inserting 1 then 2 differs from 2 then 1). Count the number of distinct ordered insertion sequences whose values sum to exactly F, modulo 1000000007. A fare of 0 has exactly one payment: insert nothing.
Input format
Line 1: two integers n and F.
Line 2: n space-separated distinct integers, the token denominations.
Output format
A single integer: the number of ordered token sequences summing to exactly F, taken modulo 1000000007.
Constraints
- 1 <= n <= 20
- 1 <= each denomination <= 1000
- 0 <= F <= 5000