Ước số fibonacci

Số \(fib(n)\) với \(n \geq 0\) được tính theo công thức sau:

• \(fib(n) = n\) nếu \(n \leq 1\).
• \(fib(n) = fib(n - 1) + fib(n - 2)\) với \(n > 1\).

Yêu cầu: Cho ba số nguyên \(a, b, M\), gọi \(u\) là ước số chung lớn nhất của \(fib(a)\) và \(fib(b)\), hãy tính phần dư của phép chia \(u\) cho \(M\).

Input

Vào từ thiết bị vào chuẩn gồm ba số nguyên dương \(a, b, M\) \((a, b, M \leq 10^{12})\)

Output

Ghi ra thiết bị ra chuẩn một số là phần dư của phép chia \(u\) cho \(M\).

Example

6 9 10

2

Scoring

Subtask \(1\) với \(70\%\) số điểm : \(a, b, M \leq 50\).

Subtask \(2\) với \(20\%\) số điểm : \(a, b, M \leq 10^9\)

Subtask \(3\) với \(10\%\) số điểm : \(a, b, M \leq 10^{12}\)