Coin change/(dp)

//problem link:https://lightoj.com/problem/coin-change-i

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int n, k;
const ll mod = 100000007;
const ll mx = 1e3 + 5;
ll dp[55][mx];
vector<ll> a;
ll c[25];
ll solve(int i, int sum) {
  if (i == a.size() || sum <= 0) {
    return (sum == 0);
  }
  if (dp[i][sum] != -1) {
    return dp[i][sum];
  }
  ll res = 0;
  for (int m = 0; m <= c[i]; m++) {
    if (sum - (m * a[i]) >= 0) {
      res += solve(i + 1, sum - (m * a[i]));
    } else {
      break;
    }
  }
  return dp[i][sum] = res % mod;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  memset(dp, -1, sizeof(dp));
  int tt, s = 1;
  cin >> tt;
  while (tt--) {
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
      int x;
      cin >> x;
      a.push_back(x);
    }
    for (int i = 0; i < n; i++) {
      cin >> c[i];
    }
    cout << "Case " << s++ << ": " << solve(0, k) % mod << "\n";
    a.clear();
    memset(c, 0, sizeof(c));
  }
  return 0;
}