#include <cstdio>

#include <iostream>

#include <cstring>

using namespace std;

typedef long long ll;

const int mo = 1e9 + ;

long long s[][],f[];

long long myc[][];

void init()

{

    myc[][]=;

    myc[][]=myc[][]=;

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

    {

        myc[i][]=;

        myc[i][i] = ;

        for(int j=;j<i;j++)

            myc[i][j]=(myc[i-][j]+myc[i-][j-])%mo;//组合数

    }

    f[]=;

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

        f[i]=(f[i-]*i)%mo;//阶乘

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

        s[i][i]=,s[i][]=;

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

    {

        for(int j=;j<=i-;j++)

        {

            s[i][j]=(j*s[i-][j]+s[i-][j-])%mo;//斯特林数

        }

    }

    return ;

}

int main()

{

    int T,n,m,i,j;

    cin>>T;

    init();

    while(T--)

    {

        cin>>n>>m;

        long long ans=;

        for(i=;i<=min(m-,n);i++)

        {

            long long now=(((myc[m][i]*s[n][i])%mo)*f[i])%mo;

            int up=min(n,m-i);

            for(j=;j<=up;j++)

            {

                ans=(ans+(f[j]*now)%mo*((myc[m-i][j]*s[n][j])%mo))%mo;

            }

        }

        cout<<ans<<endl;

    }

    return ;

}