时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
You are given three integers 
. Define a function:
%20%3D%20%5Ctext%7Blcm%7D(x%2Cb)%2B%5Cgcd(x%2Cb))
where)
denotes the least common multiple of 
and 
, and )
denotes the greatest common divisor of and . For example, %3D18%2C%20%5Cgcd(6%2C9)%3D3)
.
Let%7D(x))
denote the result of applying the function )
for 
times. That is: %7D(x)%20%3D%20f(x)%2C%20f%5E%7B(2)%7D(x)%20%3D%20f(f(x))%2C%20f%5E%7B(3)%7D(x)%20%3D%20f(f(f(x))))
and so on.
Your task is to compute the value of%7D(a))
modulo 
.
where
Let
Your task is to compute the value of
输入描述:
One line contains three space-separated integers(
).
输出描述:
Print a single integer --- the value ofmodulo
.