Description

The binomial coefficientis the number of ways of picking k unordered outcomes from n possibilities, also known as a combination or combinatorial number.

 

 

       Give n and k, you are required to calculate  mod 10000003.

Input

The input contains several test cases. The first line of the input contains one positive integer, c, denoting the number of test cases.

       Each of the following c lines contains two integers, n(0<=n<=1000) and k (0<=k<=n), denoting that you are required to calculatemod 10000003.

Output

For each test case, output one line containing mod 10000003.

Sample Input

3
1 1
10 2
954 723

Sample Output

1
45
3557658

Source

Unknown 思路：我滴娘，这道题我本来想用1245的思路去做的，但是发现连long long也存不下了，只能用数论公式：C(N, M) = C(N-1, M)+C(N-1, M-1)；

#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <vector>
using namespace std;
#define ll long long

ll n, k, num[1000+8][1000+8];
ll sum;

void init()
{
    ll sum = 1;
    num[0][0] = 1;
    for(int i = 0; i<1000+1; i++)
    {
        num[i][0] = num[i][i] = 1;
        for(int j = 1; j<i; j++)
            num[i][j] = (num[i-1][j]+num[i-1][j-1])%10000003;
    }
}

int main()
{
    init();
    int t;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%lld%lld", &n, &k);
        printf("%lld\n", num[n][k]);
    }
    return 0;
}