//暴力求解: C(n,m)=n*(n-1)*...*(n-m+1)/m!（n<=15）
long long C(int n,int m){
    long long res=1;
    for (int i = n, j = 1; j <= m; i --, j ++ )
    {
        res = res * i / j;
    }
    return res;
}

//预处理递推：C(n,m)=C(n-1,m-1)+C(n-1,m) (n<=10000)
const int N=2010;
const int mod=1e9+7;

int C[N][N];
void get_C(){
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<i;j++)
        {
            if(j==0) C[i][j]=1;
            else C[i][j]=( C[i-1][j-1]+C[i-1][j] )%mod;
        }
    }
}