LIGHT OJ 1231

 /*
       _________
      /         \
     /  _     _  \
    /   0     0   \
   |       ||     |
   |              | => HI
    \     -----   /
     \           /
      \_ _ _ _ _/
 */

#include<bits/stdc++.h>
using namespace std;
using lli = int64_t;
const int maxN = 1010;
lli grid[51][maxN];
lli solve(int coins[],int coins_count[],int idx,int k,int n){
    if(idx == n or k == 0){
        return (k == 0);
    }
    if(grid[idx][k] != -1){
        return grid[idx][k];
    }
    lli res = 0;
    for(int i = 0;i <= coins_count[idx]; i++){
        if(k - (coins[idx] * i) >= 0){
            res += solve(coins,coins_count,idx + 1,k - (coins[idx] * i),n);
        }
    }
    return grid[idx][k] = res % 100000007;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    for(int t = 1; t <= T; t++){
        memset(grid,-1,sizeof(grid));
        int n,k;
        cin >> n >> k;
        int coins[51],coins_count[51];
        for(int i = 0;i < n; i++){
            cin >> coins[i];
        }
        for(int i = 0;i < n; i++){
            cin >> coins_count[i];
        }
        cout << "Case " << t << ": " << solve(coins,coins_count,0,k,n) << "\n";
    }
}