1 #include <algorithm> 2 #include <iostream> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cstdio> 6 #include <vector> 7 #include <ctime> 8 #include <queue> 9 #include <list>10 #include <set>11 #include <map>12 using namespace std;13 #define INF 0x3f3f3f3f14 #define mod 10000000715 typedef long long LL;16 17 int val[55], num[55], dp[55][1005];18 int main()19 {20     int t, n, k;21     scanf("%d", &t);22     for(int ca = 1; ca <= t; ca++)23     {24         scanf("%d %d", &n, &k);25         for(int i = 1; i <= n; i++)26             scanf("%d", &val[i]);27         for(int i = 1; i <= n; i++){28             scanf("%d", &num[i]);29             num[i] = min(num[i], k / val[i]);30         }31         memset(dp, 0, sizeof(dp));32         for(int i = 0 ; i <= n; i++)33             dp[i][0] = 1;34         for(int i = 1; i <= n; i++)35         {36             for(int j = k; j > 0; j--)37             {38                 for(int l = 0; l <= num[i]; l++)39                 {40                     if(j - l * val[i] >= 0){41                         dp[i][j] = (dp[i-1][j-l*val[i]] + dp[i][j]) % mod;42                       //  cout << i <<" "<< j <<" "<< dp[i][j] <<endl;43                     }44 45                 }46             }47         }48         printf("Case %d: %d\n", ca, dp[n][k]);49     }50     return 0;51 }