#include <bits/stdc++.h>

 using namespace std;

 #define ll long long

 #define LL __int128

 #define ull unsigned long long

 #define mst(a,b) memset((a),(b),sizeof(a))

 #define mp(a,b) make_pair(a,b)

 #define fi first

 #define se second

 #define pi acos(-1)

 #define pii pair<int,int>

 #define pb push_back

 const int INF = 0x3f3f3f3f;

 const double eps = 1e-;

 const int MAXN = 1e4 + ;

 const int MAXM = 1e6 + ;

 const ll mod = 1e9 + ;

 ll dp[][MAXN];

 int main()

 {

 #ifdef local

     freopen("data.txt", "r", stdin);

 //    freopen("data.txt", "w", stdout);

 #endif

     int t;

     scanf("%d",&t);

     while(t--) {

         int n,q;

         scanf("%d%d",&n,&q);

         mst(dp, );

         dp[][] = ;

         for(int i = ; i <= n; i++) {

             int c,v;

             scanf("%d%d",&v,&c);

             c = ( << c) * v;

             for(int j = ; j < v; j++) dp[i][j] = dp[i - ][j];

             for(int j = v; j <= ; j++) {

                 dp[i - ][j] += dp[i - ][j - v];

                 if(dp[i - ][j] >= mod) dp[i - ][j] -= mod;

                 dp[i][j] = dp[i - ][j];

                 if(j >= c) {

                     dp[i][j] -= dp[i - ][j - c];

                     if(dp[i][j] < ) dp[i][j] += mod;

                 }

             }

         }

         while(q--) {

             int s;

             scanf("%d",&s);

             printf("%lld\n",dp[n][s]);

         }

     }

     return ;

 }