ll c[1005][1005]; const int mod=1e9+7; for (int i=0; i<=1000; ++i) { c[i][0]=c[i][i]=1; for (int j=1; j<i; ++j) c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod; }