#include<bits/stdc++.h> #define int long long using namespace std; const int inf = 0x3f3f3f3f; const int N = 1001; int dp[N][N]; //vector<int> c[N];//重量 //vector<int> w[N];//价值 //int sum[N]; int c[N]; int w[N]; const int ans = 1e9 + 9; //int s[N];//数量 //dp[i][j] //代表前i个物品时背包体积最大为j时物品最大价值 //dp[i - 1][j] 不选 //dp[i - 1][j - c[i]] + w[i] 选 signed main(){ freopen("divide.in" , "r" , stdin); freopen("divide.out" , "w" , stdout); int m; cin >> m; //dp[i][j] //表示前i个数和刚好为j的方案数 while(m --){ memset(dp , 0 , sizeof(dp)); int n; cin >> n; dp[0][0] = 1; for(int i = 1 ; i <= n ; i ++){//数 for(int j = 0 ; j <= n ; j ++){//容量 if(j >= i){ dp[i][j] = (dp[i - 1][j] + dp[i][j - i]) % ans; }else{ dp[i][j] = dp[i - 1][j]; } } }

cout << dp[n][n] % ans << endl; 
}
return 0;

}