一个有关组合数的问题

给你n个物品，每次从中取k个，问有多少种取法。

比如有4个物品，从中取2个，有6中取法：

1 2

1 3

1 4

2 3

2 4

3 4

Input

输入有多组数据。

第一行一个整数T。 (T ≤ 2000)

接下来有T行，每行两个整数n和k。 其中1 ≤ n ≤ 10^6, 0 ≤ k ≤ n.

Output

对于每组数据，输出取法总数，结果可能会很大，所以你需要把结果对1000003取余数

Sample Input 1

3

4 2

5 0

6 4

Sample Output 1

Case 1: 6

Case 2: 1

Case 3: 15

Time Limit 1000MS

Memory Limit 64MB

蒟蒻RE了2个点，（感觉就算没RE也是TLE）

求助owo

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=1000003;
ll t,n,k,a[3010][3011]={0};
int main(){
	std::ios::sync_with_stdio(false);
	cin>>t;
	for(int i=1;i<=t;i++){
		cin>>n>>k;
		if(a[n+1][k+1]!=0){
			cout<<"Case "<<i<<": "<<a[n+1][k+1]<<endl;
			continue;
		}
		a[1][1]=1;
		for(int i=2;i<=n+1;i++){
			for(int j=1;j<=i;j++){
				if(j==1)
					a[i][j]=1;
				else
					a[i][j]=(a[i-1][j]%mod+a[i-1][j-1]%mod)%mod;
			}
		}
		cout<<"Case "<<i<<": "<<a[n+1][k+1]<<endl;
	}
	return 0;
}