题目
题目描述
一日，BY大神黄犇黄大组长打完羽毛球回来，发现博士正在用魔兽地图编辑器做一个计算器的软件。
因为最近总是一些取模取模的，所以想非常快速的算出来。简而言之，就是对以下$3$个问题进行讨论。
- 给定$y, z, P$，计算$y^z ({\rm mod}~ P)$的值；
- 给定$y, z, P$，计算满足$y^x \equiv z({\rm mod}~ P)$的最小非负整数$x$；
- 给定$y, z, P$，计算$C(z, y)({\rm mod}~ P)$的值（意义为$Z$中取$Y$的组合）。
输入
第一行一个正整数$N$，描述数据组数。
接下来的$N$行，每行$4$个正整数$Sum, y, z, P$。
$Sum$表述询问类型，如上所述。对于第$2$种要求，若$x$不存在，则输出“Math Error”。
输出
要求有$N$行输出，每行一个整数，为询问的答案。
样例输入1
4
1 2 10 1000
2 3 1 1000
2 2 3 4
3 2 7 9
样例输出1
24
0
Math Error
3
样例输入2
4
2 1 2 9
3 1 6 7
1 5 3 7
1 9 2 8
样例输出2
Math Error
6
6
1
数据范围
| 操作$1$ | 操作$2$ | 操作$3$ | |
| $1 \sim 4$ | 操作个数$< 501$。保证$y, z, p < 10^9$。 | 操作个数为$0$。 | 操作个数为$0$。 |
| $5 \sim 10$ | 操作个数$< 51$。保证$y, z, P < 10^3$。$P$不一定为质数。 | 操作个数$< 11$。保证$y, z < 10^3, P < 10^9$。$P$不一定为质数。 | |
| $11 \sim 16$ | 操作个数$< 31$。保证$y, z, P < 10^9$。而且$P$为质数。 | 操作个数$< 31$。保证$y, z < 10^7, P < 10^5$。而且$P$为质数。 | |
| $17 \sim 20$ | 操作个数$< 51$。保证$y, z, P < 10^9$。$P$不一定为质数。 | 操作个数$< 51$。保证$y, z < 10^6, P < 10^9$。$P$不为质数。 |