#MX145. 快速幂

快速幂

题目描述

给出三个整数 A,B,MA,B,M。

若 $x=\overbrace{111\ldots 1}^{A\text{\tt个}},y=\overbrace{111\ldots 1}^{B\text{\tt个}}$。

请你输出 lcm(x,y) mod M\text{lcm}(x,y) \bmod M,其中 lcm\text{lcm} 表示最小公倍数。

输入格式

第一行给定正整数 A,B,MA,B,M。

输出格式

输出一行包含 11 个整数,表示答案。

样例 1 输入

2 3 100

样例 1 输出

21

样例解释

lcm(11,111)=1221\text{lcm}(11,111)=1221

样例 2 输入

9 8 998244353

样例 2 输出

164769454

样例 3 输入

1088 1087 998244353

样例 3 输出

619129562

样例 4 输入

1088 1087 8100000

样例 4 输出

5954321

数据规模与约定

对于 20%20\% 的数据,1≤A,B≤10,M=9982443531 \leq A,B \leq 10,M=998244353。

对于另外 20%20\% 的数据,1≤A,B≤2000,M=9982443531 \leq A,B \leq 2000,M=998244353。

对于另外 20%20\% 的数据,gcd⁡(A,B)=1,M=998244353\gcd(A,B)=1,M=998244353。

对于前 80%80\% 的数据,M=998244353M=998244353。

对于 100%100\% 的数据,1≤A,B≤1018,1≤M≤1091 \leq A,B \leq 10^{18},1 \leq M \le 10^9