虫群之心

题目信息

时间限制: 1s

空间限制: 256M

输入文件: factorial.in

输出文件: factorial.out

题目描述

一只小狗的力量是薄弱的，它的战斗力仅有 1。

两只小狗也改变不了任何事情，它们的战斗力是 $1\times 2 = 2$。

当三只小狗聚在一起，在虫群女王的心灵指挥下，它们的战斗力是 $1\times 2\times 3 = 6$。

如果成千上万只小狗聚在一起，它们共同协作的力量将难以估计！$m$ 只小狗的战斗力是 $m!$，对于给定的 $m$ 请求出这支小狗群的战斗力，因为答案很大，所以只需要输出对给定的 $p$ 取模后的结果即可。

输入格式

第一行一个数 $T$，表示测试数据的组数。

接下来 $T$ 行，每行两个正整数 $m, p$，表示一组数据，含义如题所示。

输出格式

一共 $T$ 行，每行一个正整数，表示这支小狗群战斗力对 $p$ 取模后的结果。

样例

样例输入 1

2
2 3
5 7

样例输出 1

2
1

数据范围与提示

• subtask1(20 pts): $T=100, p \leq 1000, m \leq 1000$
• subtask2(40 pts): $T=10, p \leq 10^6, m \leq 10^6$
• subtask3(40 pts): $T=1000, p \leq 3\times 10^9, p-1000 \leq m \leq 3\times 10^9$

保证对于所有点，$\mathrm{p}$ 是质数。