/*

 推导公式

 a[n] = 2^(n-1) + (n-2)*2^(n-3)

 */

 #include<stdio.h>

 #include<math.h>

 #include<algorithm>

 using namespace std;

 typedef long long int64;

 const int64 mod = 1e9+;

 int64 FastPow( int64 n,int64 m ){//n^m

     int64 sum = ;

     while( m>= ){

         if( m%== ){

             sum *= n;

             sum %= mod;

         }

         n *= n;

         n %= mod;

         m/=;

     }

     return sum;

 }

 int main(){

     int T;

     scanf("%d",&T);

     while( T-- ){

         int64 n,k;

         //scanf("%lld%lld",&n,&k);

         scanf("%I64d%I64d",&n,&k);

         if( k>n ){

             printf("0\n");

             continue;

         }

         if( k==n ){

             printf("1\n");

             continue;

         }

         int64 delta = k-;

         int64 Index = n-delta;

         if( Index== ){

             printf("1\n");

             continue;

         }

         if( Index== ){

             printf("2\n");

             continue;

         }

         //printf("%lld\n",(FastPow2(2,Index-1)%mod+FastPow2(2,Index-3)*(Index-2)%mod)%mod);

         printf("%I64d\n",(FastPow(,Index-)%mod+FastPow(,Index-)*(Index-)%mod)%mod);

     }

     return ;

 }