Recently in Teddy's hometown there is a competition named "Cow Year Blow Cow".N competitors had took part in this competition.The competition was so intense that the rank was changing and changing. 
Now the question is: 
How many different ways that n competitors can rank in a competition, allowing for the possibility of ties. 
as the answer will be very large,you can just output the answer MOD 20090126. 
Here are the ways when N = 2: 
P1 < P2 
P2 < P1 
P1 = P2 

2

2

3

3

13

代码如下：

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define ll long long

using namespace std;

const int N = ;

const int MOD = ;

ll dp[N][N], ans[N], fac[N];

void init()

{

    fac[] = ;

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

        fac[i] = (fac[i-]*i)%MOD;   //阶乘初始化

    memset(dp, , sizeof(dp));

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

    {

        dp[n][] = ;

        dp[n][n] = ;

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

        {

            dp[n][k] = dp[n-][k-]+k*dp[n-][k];

            dp[n][k] %= MOD;

        }

    }

}

int main()

{

    int T, n;

    init();

    cin>>T;

    while(T--)

    {

        cin>>n;

        ll ans = ;

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

            ans = (ans + fac[i]*dp[n][i]) % MOD;

        cout<<ans<<endl;

    }

    return ;

}