【模板】快速阶乘算法

题目背景

有一天,NaCly_Fish 无意间看到一种高效求阶乘模大质数的算法,但是她太菜,并不会写。 于是她就暴力造了数据,请您帮忙写出 std 吧。 什么,您问为什么不保证模数可以 NTT? 那样的话就可能被打表水过,或者答案就爆 int 了。 反正您是神仙,肯定能秒掉这题。

题目描述

给你正整数 $n$,和一个质数 $p$,你需要求出: $$ n! \text{ mod } p$$ 有 $T$ 组数据。

输入输出格式

输入格式


第一行一个正整数 $T$,表示数据组数。 接下来 $T$ 行,每行两个正整数 $n,p$,意义如题目描述。

输出格式


输出 $T$ 行,表示每组数据的答案。

输入输出样例

输入样例 #1

4
16777216 998244353
72267859 998244353
2333333 19260817
1919810 2147481811

输出样例 #1

789885751
569626621
16351109
1416439247

说明

### 数据范围: 对于 $10\%$ 的数据:$p = 998244353$ 对于另外 $10\%$ 的数据:$p = 1004535809$ 对于 $100\%$ 的数据:$1\le n < p \le 2^{31}-1$,$1 \le T \le 5$ 保证 $p$ 为质数。 【提示】 请确保你的算法时间复杂度不高于 $\Theta(\sqrt n \log n)$,时限为 std 的十倍以上。