All submissions for this problem are available.
Chef recently visited a strange land with strange currency. One day Chef needed to make change to pay for an item with coins, and wondered how many ways it could be done, assuming an infinite supply of each type of coins. Two ways are considered different if there is some coin that appears a different number of times in each sum. The answer may be very large, so Chef only needs to know the remainder when the answer is divided by 1000000007 (109 + 7).
Chef noticed something curious about the currency in question: not only do all coins have different denominations, but no two denominations of coin share any common factor other than 1.
The first line of the input contains an integer T, denoting the number of test cases. The description of T test cases follows. The first line of each test case contains two space-separated integers N and C, denoting the number of different coin types and the desired total coinage, respectively. The second line contains N space-separated integers D1, D2, ..., DN, denoting the denominations of the coins.
For each test case, output on a separate line the number of ways to make the desired amount of change, modulo 1000000007.
- 1 ≤ T ≤ 5
- 1 ≤ N ≤ 50
- 1 ≤ C ≤ 10100
- 1 ≤ Di ≤ 500
- All Di are pairwise distinct and pairwise relatively prime.
Input: 3 3 16 3 4 5 2 2000000014 1 2 3 380134 23 5 2 Output: 4 1 314159265
Example case 1. There are 4 ways to make a total of 16 using coins with values 3, 4 and 5:
- 16 = 4 + 4 + 4 + 4
- 16 = 3 + 4 + 4 + 5
- 16 = 3 + 3 + 5 + 5
- 16 = 3 + 3 + 3 + 3 + 4
Example case 2. There are 1000000008 ways to make the desired change. The remainder when divided by 1000000007 is 1.
|Tags||advanced-math, hard, march13, maths, pieguy|
|Time Limit:||3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.