楊輝三角是個經典的數據模型，它形如：

KACA現在不滿足求這些很小的數，他想要知道當nn和mm都比較大的時候的楊輝三角第nn行第mm列的值是多少。

輸入

第一行有一個數字T(T≤2000)T(T≤2000)代表有TT組數據。

下面有T行，每一行有兩個數字n(1≤n≤106),m(0≤m≤n)n(1≤n≤106),m(0≤m≤n)。

輸出

對于每一組輸入，你應該輸出一個數字，代表第nn行第mm列楊輝三角的數字，因為數字可能很大，所以你只需要輸出其對10000031000003取模后的結果。

樣例輸入

31 12 13 2
樣例輸出
112
代碼
題目鏈接 http://acm.hpu.edu.cn/PRoblem.php?id=1076
mod世界沒有除法，但是有逆元，可以實現“除法”比如 n (mod MOD) 我要除m，設m的逆元為t，那么結果就是 n*t (mod MOD)
#include<stdio.h>#define MOD 1000003#define MAX_N 1000003typedef long long LL;LL fact[MAX_N];LL inv[MAX_N];void init(){    fact[0]=1;    for(int i=1;i<MAX_N;i++)        fact[i]=(fact[i-1]*i)%MOD;    inv[1]=1;    for(int i=2;i<MAX_N;i++)        inv[i]=(inv[MOD%i]*(MOD-MOD/i))%MOD;}int main(){    int T,n,m;init();    scanf("%d",&T);    while(T--){        scanf("%d%d",&n,&m);        printf("%lld/n",(fact[n-1]*inv[fact[n-m]]*inv[fact[m-1]])%MOD);    }    return 0;}