Processing math: 100%
Coins 2 - MarisaOJ: Marisa Online Judge

Coins 2

Time limit: 1000 ms
Memory limit: 256 MB
There are n types of coins in Gensokyo. The ith type is worth Ai. Marisa has to pay a debt of k, how many **ordered** ways of choosing coins to produce k? ### Input - The first line contains 2 integers n,k. - The second line contains n distinct integers Ai. It is guaranteed that no 2 coin types worth the same. ### Output - Print one integer, the number of ways modulo 109+7. ### Constraints - 1≤n≤1000. - 1≤k≤105. - 1≤Ai≤105. ### Example Input: 34123 Output: 4 Note: There are 4 ways: - 1+1+1+1 - 1+1+2 - 1+3 - 2+2