题目描述

这是一道计算题，你需要计算下面三个算式的值： (1)给定$P,y,z$，求$y^z\bmod P$。 (2)给定$P,y,z$，求满足$y^x≡z(\bmod P)$的最小非负整数解。 (3)给定$P,y,z$，求$C_z^y\bmod P$，其中$C_z^y$为$z$中取$y$的组合数。

输入

第一行一个整数$N$表示数据组数。 接下来$N$行每行四个整数$type,y,z,P$。$type$表示询问类型，保证$type∈\{1,2,3\}$。

输出

对于每组数据输出一行表示答案。对于问题类型（2）若$x$不存在则输出“Math Error”（不含引号）。

输入样例

6
2 2 3 4
3 2 7 9
2 1 2 9
3 1 6 7
1 5 3 7
1 9 2 8

输出样例

Math Error
3
Math Error
6
6
1

提示

【数据规模与约定】

测试点	问题类型1约定	问题类型2约定	问题类型3约定
$1\sim 4$	问题个数不超过$500$，$y,z,P≤10^9$	问题个数为$0$	问题个数为$0$
$5\sim 10$		问题个数不超过$50$，$y,z,P≤10^3$	问题个数不超过$10$，$y,z≤10^3，P≤10^9$
$11\sim 16$		问题个数不超过$30$，$y,z,P≤10^9$,$P$为质数	问题个数不超过$30$，$y,z≤10^7$，$P≤10^9$，$P$为质数
$17\sim 20$		问题个数不超过$50$，$y,z,P≤10^9$	问题个数不超过$50$，$y,z≤10^6$，$P≤10^9$

对于100%的数据，若$P$不为质数，且$P = \prod_{i=1}^{k}P_{i}^{a_i}$ ，其中$p_i$是互不相同的质数，保证 $P_i^{a_i}≤10^5$ 。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共5个测试点，非原站或官方原始数据。总分100分。