题目描述
你需要实现一个支持下列 $14$ 种指令的非负整数计算器。每份输入仅包含一条指令，输出该指令的计算结果。
除第 $6$ 种指令的参数 $a$ 和第 $7$ 种指令的输出使用二进制外，所有输入、输出的整数均使用十进制。所有整数均不带正负号、没有多余前导零，零写作 0。
下文中，$x\bmod m$ 表示 $x$ 除以正整数 $m$ 所得的余数，其取值范围为 $[0,m)$；$\lfloor x\rfloor$ 表示不超过 $x$ 的最大整数。
指令 1：加法
指令格式：1 a b。
输出一行一个整数 $a+b$。
指令 2：减法
指令格式：2 a b。
保证 $a\ge b$。输出一行一个整数 $a-b$。
指令 3：乘法
指令格式：3 a b。
输出一行一个整数 $ab$。
指令 4：除法与余数
指令格式：4 a b。
保证 $b>0$。第一行输出商 $\left\lfloor\dfrac{a}{b}\right\rfloor$，第二行输出余数 $a\bmod b$。
指令 5：模幂
指令格式：5 a b m。
保证 $m>0$。输出一行一个整数 $a^b\bmod m$。
规定 $0^0=1$。当 $m=1$ 时，答案为 $0$。
指令 6：二进制转十进制
指令格式：6 a。
此处 $a$ 以二进制输入，仅由字符 0 和 1 组成。输出一行，给出 $a$ 的十进制表示。
指令 7：十进制转二进制
指令格式：7 a。
此处 $a$ 以十进制输入。输出一行，给出 $a$ 的二进制表示。
指令 8：按位运算
指令格式：8 a b。
将 $a,b$ 写成二进制，并在较短的表示左侧补零使二者等长，分别计算以下结果：
- 第一行输出按位与 $a\operatorname{and}b$；每一位仅当两个对应位均为 $1$ 时为 $1$。
- 第二行输出按位或 $a\operatorname{or}b$；每一位当至少一个对应位为 $1$ 时为 $1$。
- 第三行输出按位异或 $a\operatorname{xor}b$；每一位当两个对应位不同时为 $1$。
三个结果均以十进制输出。
指令 9：最小公倍数
指令格式：9 a b。
输出一行一个整数 $\operatorname{lcm}(a,b)$。当 $a,b$ 均为正整数时，它表示二者的最小正公倍数。
当 $a,b$ 中至少有一个为 $0$ 时，规定答案为 $0$，包括 $a=b=0$ 的情况。
指令 10：模逆
指令格式：10 a m。
保证 $m\ge2$ 且 $\gcd(a,m)=1$，其中 $\gcd$ 表示最大公约数。
输出唯一的整数 $x$，满足
$$ 0\le x
输入中的 $a$ 可以大于或等于 $m$。
指令 11：组合数
指令格式：11 a b。
保证 $0\le b\le a$。输出一行一个整数
$$ \binom ab=\frac{a!}{b!(a-b)!}, $$
即从 $a$ 个不同元素中选取 $b$ 个元素的方案数。
指令 12：Fibonacci 数取模
指令格式：12 a m。
Fibonacci 数列满足
$$ F_0=0,\qquad F_1=1,\qquad F_n=F_{n-1}+F_{n-2}\quad(n\ge2). $$
保证 $m>0$。输出一行一个整数 $F_a\bmod m$。
当 $m=1$ 时，答案为 $0$。
指令 13：整数开方
指令格式：13 a b。
保证 $a\ge1$。输出一行一个整数 $\left\lfloor\sqrt[a]{b}\right\rfloor$，即满足
$$ x^a\le b<(x+1)^a $$
的非负整数 $x$。
指令 14：阶乘
指令格式：14 n。
输出一行一个整数 $n!$。当 $n\ge1$ 时，$n!=1\times2\times\cdots\times n$；规定 $0!=1$。
输入格式
输入仅一行，包含一条指令。第一个整数为指令编号 $\mathrm{op}$，满足 $1\le\mathrm{op}\le14$，其后依次为该指令所需的参数，具体格式见上文。
相邻整数之间以一个空格分隔。输入没有测试组数。
输出格式
按照输入的指令输出计算结果，每行一个整数。
第 $4$ 种指令输出两行，第 $8$ 种指令输出三行，其余指令均输出一行。
所有结果都必须精确输出，不带正负号、没有多余前导零。结果为零时输出 0；除第 $7$ 种指令外，所有结果均以十进制输出。
数据范围
对于所有测试数据，输入参数均为非负整数，并满足对应指令中给出的保证。
记 $L_{10}(x)$ 为 $x$ 的十进制位数，$L_2(x)$ 为 $x$ 的二进制位数，并规定 $L_{10}(0)=L_2(0)=1$。各指令的参数范围如下；表中列出的是输入参数的限制，计算结果的位数不受这些上界限制。
| 指令编号 | 参数范围 |
|---|---|
| $1,2$ | $L_{10}(a),L_{10}(b)\le10^6$ |
| $3$ | $L_{10}(a),L_{10}(b)\le262144$ |
| $4$ | $L_{10}(a),L_{10}(b)\le200000$，$b>0$ |
| $5$ | $L_{10}(a)\le200000$，$0\le b\le10^{18}$，$1\le m$ 且 $L_{10}(m)\le20000$ |
| $6$ | $L_2(a)\le10^6$ |
| $7$ | $L_{10}(a)\le200000$ |
| $8$ | $L_{10}(a),L_{10}(b)\le200000$ |
| $9$ | $L_{10}(a),L_{10}(b)\le100000$ |
| $10$ | $L_{10}(a),L_{10}(m)\le100000$，$m\ge2$，$\gcd(a,m)=1$ |
| $11$ | $0\le b\le a\le10^6$ |
| $12$ | $0\le a\le10^{18}$，$1\le m$ 且 $L_{10}(m)\le20000$ |
| $13$ | $1\le a\le64$，$L_{10}(b)\le100000$ |
| $14$ | $0\le n\le100000$ |
第 $5,12$ 种指令中的 $m$ 为模数本身，可以是任意满足范围的正整数。
输入输出样例
以下每组样例均为一份独立的输入，样例编号与指令编号相同。
样例 #1：加法
样例输入 #1
1 99999999999999999999 1
样例输出 #1
100000000000000000000
样例 #2：减法
样例输入 #2
2 100000000000000000000 1
样例输出 #2
99999999999999999999
样例 #3：乘法
样例输入 #3
3 12345678901234567890 98765432109876543210
样例输出 #3
1219326311370217952237463801111263526900
样例 #4：除法与余数
样例输入 #4
4 12345678901234567890 1000000000
样例输出 #4
12345678901 234567890
样例 #5：模幂
样例输入 #5
5 7 100 360
样例输出 #5
241
样例 #6：二进制转十进制
样例输入 #6
6 101101
样例输出 #6
45
样例 #7：十进制转二进制
样例输入 #7
7 45
样例输出 #7
101101
样例 #8：按位运算
样例输入 #8
8 10 12
样例输出 #8
8 14 6
样例说明 #8
$10$ 和 $12$ 的二进制表示分别为 1010 和 1100。按位与、按位或、按位异或的结果分别为 1000、1110、0110，对应十进制的 $8,14,6$。
样例 #9：最小公倍数
样例输入 #9
9 12 18
样例输出 #9
36
样例 #10：模逆
样例输入 #10
10 3137 3120
样例输出 #10
2753
样例说明 #10
$3137\times2753\equiv1\pmod{3120}$，且 $0\le2753<3120$。
样例 #11：组合数
样例输入 #11
11 100 50
样例输出 #11
100891344545564193334812497256
样例 #12：Fibonacci 数取模
样例输入 #12
12 100 1000
样例输出 #12
75
样例 #13：整数开方
样例输入 #13
13 3 1000000000000000000000000000001
样例输出 #13
10000000000
样例说明 #13
被开方数为 $10^{30}+1$，不是完全立方数。由于
$$ (10^{10})^3\le10^{30}+1<(10^{10}+1)^3, $$
所以答案为 $10^{10}$。
样例 #14：阶乘
样例输入 #14
14 30
样例输出 #14
265252859812191058636308480000000