# Coin Change(Finite Supply)

Hard
0/120
Contributed by

## Problem statement

You are given an array of integers ‘coins’ denoting the denomination of coins and another array of integers ‘freq’ denoting the number of coins of each denomination.

You have to find the number of ways to make the sum ‘V’ by selecting some(or all) coins from the array.

The answer can be very large. So, return the answer modulo 1000000007.

For Example :
``````‘N’ = 3, ‘coins’ = {1, 2, 3}, ‘freq’ = {1, 1, 3}, ‘V’ = 6

For the given example, we can make six by using the following coins:
{1, 2, 3}
{3. 3}
``````
Detailed explanation ( Input/output format, Notes, Images )
Constraints :
``````1 <= T <= 10
1 <= N <= 100
1 <= coins[i] <= 100
1 <= freq[i] <= 100
1 <= V <= 100

Time limit: 1 sec
``````
##### Sample Input 1 :
``````2
3
1 2 4
1 1 1
7
3
1 2 4
2 3 2
7
``````
##### Sample Output 1 :
``````1
2
``````
##### Explanation For Sample Input 1 :
``````In the first test case, there is only one possible way to make the sum equal to 7 i.e., taking all the coins. Hence answer is 1.

In the second test case, You can make the sum seven by using the following coins:
{1, 2, 4}, {1, 2, 2, 2}. Hence the answer is 2.
``````
##### Sample Input 2 :
``````2
4
1 11 7 6
1 2 3 1
10
3
5 1 2
1 1 3
6
``````
##### Sample Output 2 :
``````0
2
``````
Console