Points:
1400 (p)
Time limit:
1.0s
Memory limit:
512M
Input:
stdin
Output:
stdout
Consider a money system consisting of \(n\) coins. Each coin has a positive integer value. Your task is to calculate the number of distinct ordered ways you can produce a money sum \(x\) using the available coins.
For example, if the coins are \(\{2,3,5\}\) and the desired sum is \(9\), there are \(3\) ways:
- \(2+2+5\)
- \(3+3+3\)
- \(2+2+2+3\)
Input
- The first input line has two integers \(n\) and \(x\): the number of coins and the desired sum of money.
- The second line has \(n\) distinct integers \(c_1,c_2,\ldots,c_n\): the value of each coin.
Output
- Print one integer: the number of ways modulo \(10^9+7\).
Constraints
- \(1 \leq n \leq 100\)
- \(1 \leq x \leq 10^6\)
- \(1 \leq c_i \leq 10^6\)
Example
Sample input
3 9
2 3 5
Sample output
3
Comments
ad tăng cho python 3 thêm thời gian được không ạ,chứ nó ra kết quả đúng nhưng bị time:((
Cảm ơn bạn superman1236969 đã góp ý bản dịch!