1231 - Coin Change (I)

#include<bits/stdc++.h>
using namespace std;
 
#define mod 100000007
 
int dp[55][1010],coin[55],c[55],n,k,T;
 
int call(int i, int amount)
{
    if(i >= n)
    {
        if(amount == k)
            return 1;
        else
            return 0;
    }
 
    if(amount > k)
        return 0;
    if(amount == k)
        return 1;
 
    if(dp[i][amount] != -1)
        return dp[i][amount];
 
    int ret1=0, ret2=0;
 
    for(int a=1; a<=c[i]; a++)
    {
        if(amount+coin[i]*a <= k)
            ret1 += call(i+1,amount+coin[i]*a)%mod;
        else
            break;
    }
    ret2 = call(i+1,amount)%mod;
 
    return dp[i][amount] = (ret1 + ret2)%mod;
}
 
int main()
{
    int i,C=1;
    //freopen("1231 - Coin Change (I).txt", "r", stdin);
    cin >> T;
    while(T--)
    {
        memset(dp, -1, sizeof(dp));
        cin >> n >> k;
        for(i=0; i<n; i++)
            cin >> coin[i];
        for(i=0; i<n; i++)
            cin >> c[i];
        cout << "Case " << C++ << ": " << call(0,0) << endl;
     }
    return 0;
}