#include<bits/stdc++.h>

using namespace std;

#define MAXN 1000010

const int P = 1e9 + ;

int T,n,m,ans;

int f[MAXN],fac[MAXN],inv[MAXN];

inline int power(int a,int n)

{

        int res = ,b = a;

        while (n)

        {

                if (n & ) res = 1ll * res * b % P;

                b = 1ll * b * b % P;

                n >>= ;

        }

        return res;

}

inline void init()

{

        int i;

        f[] = ;

        f[] = ;

        f[] = ;

        for (i = ; i < MAXN; i++) f[i] = 1ll * (i - ) * (f[i-] + f[i-]) % P;

        fac[] = ;

        for (i = ; i < MAXN; i++) fac[i] = 1ll * fac[i-] * i % P;

        inv[MAXN-] = power(fac[MAXN-],P-);

        for (i = MAXN - ; i >= ; i--) inv[i] = 1ll * inv[i+] * (i + ) % P;

}

inline int C(int n,int m)

{

        if (n < m) return ;

        if (m == ) return ;

        return 1ll * fac[n] * inv[m] % P * inv[n-m] % P;

}

int main()

{

        init();

        scanf("%d",&T);

        while (T--)

        {

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

                ans = 1ll * C(n,n-m) * f[n-m] % P;

                printf("%d\n",ans);

        }

        return 

}