题目描述
给出三个整数 A,B,M。
若 $x=\overbrace{111\ldots 1}^{A\text{\tt个}},y=\overbrace{111\ldots 1}^{B\text{\tt个}}$。
请你输出 lcm(x,y)modM,其中 lcm 表示最小公倍数。
输入格式
第一行给定正整数 A,B,M。
输出格式
输出一行包含 1 个整数,表示答案。
样例 1 输入
2 3 100
样例 1 输出
21
样例解释
lcm(11,111)=1221
样例 2 输入
9 8 998244353
样例 2 输出
164769454
样例 3 输入
1088 1087 998244353
样例 3 输出
619129562
样例 4 输入
1088 1087 8100000
样例 4 输出
5954321
数据规模与约定
对于 20% 的数据,1≤A,B≤10,M=998244353。
对于另外 20% 的数据,1≤A,B≤2000,M=998244353。
对于另外 20% 的数据,gcd(A,B)=1,M=998244353。
对于前 80% 的数据,M=998244353。
对于 100% 的数据,1≤A,B≤1018,1≤M≤109