#include<iostream>
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int dp[2003][2003];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int text;
cin>>text;
while(text--)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int n;
cin>>n;
int sum = 0;
int i,j;
for(i = 1;i <= n; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
dp[i][1] = 1;
dp[i][i] = 1;
}
for(i = 3;i <= n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
for(j = 2;j <= i-1;j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
dp[i][j] = (dp[i-1][j-1] + dp[i-1][j] * j) %1000;
}
}
for(i = 1;i <= n;i++)
sum = (sum + dp[n][i])%1000;
cout<<sum%1000<<endl;
}
return 0;
}