杨辉三角是个经典的数据模型，它形如：

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;}