hdu5000Clone dp

//        
//      n   
//     a               b
//  b     
//            
//                            
//          a , c                  
//       
//      ，          sum/2   
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std ;
const int maxn = 2010 ;
typedef long long ll ;
const int mod = 1e9+7  ;
int dp[maxn][maxn] ;
int a[maxn] ;
int main()
{
    int t ;
    scanf("%d" , &t) ;
    while(t--)
    {
        int n ;
        scanf("%d"  , &n) ;
        for(int i = 1;i <= n;i++)
        scanf("%d" , &a[i]) ;
        memset(dp , 0 , sizeof(dp)) ;
        for(int i = 0;i <= a[1];i++)
        dp[1][i] = 1 ;
        int sum = a[1] ;
        for(int i = 2;i <= n;i++)
        {
            sum += a[i] ;
            for(int j = 0;j <= sum;j++)
              for(int k = j;k >= 0 && k >= j - a[i];k--)
              dp[i][j] = (dp[i][j] + dp[i-1][k])%mod ;
        }
        cout<<dp[n][sum/2]<<endl;
    }
    return 0  ;
}