配列の組み合わせ——luscaの定理

/**************************************************************

    Problem: 2982

    User: huhuuu

    Language: C++

    Result: Accepted

    Time:236 ms

    Memory:1272 kb

****************************************************************/

 

#include<iostream>

#include<stdio.h>

using namespace std;

 

int pow_mod(int a,int n,int p)

{

    int ans=1,t=a;

    while(n)

    {

        if(n&1)

            ans=(long long)ans*t%p;

        t=(long long)t*t%p;

        n>>=1;

    }

    return ans;

}

int cal(int n,int m,long p)

{

    if(m>n-m) m=n-m;

    int ans=1;

    for(int i=1;i<=m;i++)

    {

        ans=(long long)ans*(n-i+1)%p;

        int a=pow_mod(i,p-2,p);

        ans=(long long)ans*a%p;

    }

    return ans;

}

int com_mod(int n,int m,long p)

{

    if(n<m)return 0;

    return cal(n,m,p);

}

int lucas(int n,int m,long p)

{

    int r=1;

    while(n&&m&&r)

    {

        r=(long long)r*com_mod(n%p,m%p,p)%p;

        n/=p;

        m/=p;

    }

    return r;

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        int n,m,p;

        scanf("%d%d",&n,&m);p=10007;

        printf("%d
",lucas(n,m,p));

 

    }

}