30分做法

因为n最大是10，所以n!最大只有3628800。所以直接用裸的快速幂即可。

100分做法

首先此时n最大为20，显然n!已经达到longlong范围了，而快速幂中需要两个longlong的数相乘会爆longlong，此时介绍四种做法。（四种做法空间复杂度均为o(1)，下面不再赘述）。

1.普通快速乘，总体时间复杂度o(logb*logp)

运用类似于快速幂的思想，把两个longlong的数的乘法变成加法，加logp次，这样就可以满足不爆longlong了。代码如下：

typedef long long LL;
class Solution
{
public:
    /**
     * 返回式子的答案
     * @param a long长整型
     * @param b long长整型
     * @param n long长整型
     * @return long长整型
     */
    LL qmul(LL x, LL y, LL mod){
    x%=mod; 
    LL ret = 0;
    while(y) {
        if(y & 1)
            ret = (ret + x) % mod;
            x = x * 2 % mod;
            y >>= 1;
        }
        return ret;
    }
    LL Mode(LL a, LL b,LL mode)
    {
        LL sum = 1;
        while (b)
        {
            if (b%2)
            {
                sum =qmul(sum,a,mode);
                b--;
            }
            b/=2;
            a=qmul(a,a,mode);
        }
        return sum;
    }
    long long answerofformula(long long a, long long b, long long n)
    {
        // write code here
        for(int i=n-1;i>=2;i--)n*=i;
        return Mode(a,b,n);
    }
};

2.o(1)快速乘，总体时间复杂度o(logb)

此方法是通过数学的推导利用小数进行将快速乘变为o(1)的操作，但是由于涉及小数可能会引发精度问题，在数据很多时可能根据写法不同会被卡，但是由于本题是每次询问都是单组数据实际按照概率来说被卡的几率极低，而且根据写法的不同也不能通过较少的数据统一卡掉o(1)快速乘，所以还是能通过的。但是不是很建议用这种做法，下面给出参考代码：

typedef long long LL;
class Solution
{
public:
    /**
     * 返回式子的答案
     * @param a long长整型
     * @param b long长整型
     * @param n long长整型
     * @return long长整型
     */
    LL qmul(LL x,LL y,LL MOD)
    {
        x=x%MOD,y=y%MOD;
        return ((x*y-(LL)(((long double)x*y+0.5)/MOD)*MOD)%MOD+MOD)%MOD;
    }
    LL Mode(LL a, LL b,LL mode)
    {
        LL sum = 1;
        while (b)
        {
            if (b%2)
            {
                sum =qmul(sum,a,mode);
                b--;
            }
            b/=2;
            a=qmul(a,a,mode);
        }
        return sum;
    }
    long long answerofformula(long long a, long long b, long long n)
    {
        // write code here
        for(int i=n-1;i>=2;i--)n*=i;
        return Mode(a,b,n);
    }
};

3.__int128，总体时间复杂度o(logb)

黑科技，但是编译器和系统限制本地很难调试，具体看代码吧：

typedef long long LL;
class Solution
{
public:
    /**
     * 返回式子的答案
     * @param a long长整型
     * @param b long长整型
     * @param n long长整型
     * @return long长整型
     */
    LL Mode(LL a, LL b,LL mode)
    {
        __int128 aa=a;
        __int128 sum = 1;
        while (b) {
            if (b%2) {
                sum =sum*aa%mode;
                b--;
            }
            b/=2;
            aa=aa*aa%mode;
        }
        long long sum2=sum;
        return sum2;
    }
    long long answerofformula(long long a, long long b, long long n)
    {
        // write code here
        for(int i=n-1;i>=2;i--)n*=i;
        return Mode(a,b,n);
    }
};

4.Montgomery modular multiplication，总体时间复杂度o(logb)