#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

#include<map>

#include<set>

#include<queue>

#include<stack>

#include<iostream>

using namespace std;

typedef long long LL;

const double pi=acos(-1.0),eps=1e-;

void File()

{

    freopen("D:\\in.txt","r",stdin);

    freopen("D:\\out.txt","w",stdout);

}

inline int read()

{

    char c = getchar();  while(!isdigit(c)) c = getchar();

    int x = ;

    while(isdigit(c)) { x = x *  + c - ''; c = getchar(); }

    return x;

}

const int maxn=+;

int dp[maxn][maxn][][],f[maxn][maxn][][];

int mod=1e9+;

int T,n,s,a[maxn];

int main()

{

    scanf("%d",&T); while(T--)

    {

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

        for(int i=;i<=n;i++) scanf("%d",&a[i]);

        memset(dp,,sizeof dp); dp[][][][]=;

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

        {

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

            {

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

                {

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

                    {

                        int num=;

                        num=(num+dp[i-][j][p][h])%mod;

                        if(j-a[i]>=) num=(num+dp[i-][j-a[i]][p][h])%mod;

                        if(p->=&&j>=a[i]) num=(num+dp[i-][j-a[i]][p-][h])%mod;

                        if(h->=) num=(num+dp[i-][j][p][h-])%mod;

                        dp[i][j][p][h]=num;

                    }

                }

            }

        }

        LL ans=;

        for(int i=;i<=s;i++) ans=(ans+dp[n][i][][])%mod;

        printf("%lld\n",(ans*)%(LL)mod);

    }

    return ;

}