普及模拟赛 13 - E

时空限制

时间限制 $2\text{s}$，内存限制 $1024\text{MB}$。

题目描述

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

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

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

输入格式

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

输出格式

输出一行包含 $1$ 个整数，表示答案。

样例输入1

2 3 100

样例输出1

21

样例解释

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

样例输入2

9 8 998244353

样例输出2

164769454

样例输入3

1088 1087 998244353

样例输出3

619129562

样例输入4

1088 1087 8100000

样例输出4

5954321

数据范围

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

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

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

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

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