#include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int mod = 1e9 + ;

 int a[];

 int dp[][];

 int sm[];

 int add(int a, int b) {

     a += b;

     if (a >= mod)

         a -= mod;

     return a;

 }

 int main() {

     int t;

     scanf("%d", &t);

     while (t--) {

         int n, sum = ;

         scanf("%d", &n);

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

             scanf("%d", &a[i]), sum += a[i];

         sort(a + , a +  + n, greater<int>());

         dp[][] = ;

         sm[] = ;

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

             for (int j = sum; j >= a[i]; j--) {

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

                 sm[j] = add(sm[j], dp[i][j]);

             }

         }

         int ans = ;

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

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

                 if (j >= sum - j && j - a[i] <= sum - j)

                     ans = add(ans, dp[i][j]);

                 dp[i][j] = ;

                 sm[j] = ;

             }

         }

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

     }

 }