F. Fibonacci
time limit per test
0.25 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The Fibonacci sequence $$$(f_n)$$$ is defined as follows:

$$$$$$f_n = \begin{cases} 0 & n = 0, \\ 1 & n = 1, \\ f_{n-1} + f_{n-2} & n \geq 2. \end{cases}$$$$$$

For example, the first $$$6$$$ terms of this sequence are $$$0, 1, 1, 2, 3$$$, and $$$5$$$, and $$$f_{9} = 34$$$.

Given two integers $$$a$$$ and $$$b$$$ ($$$1 \leq a,b \leq 10^9 + 9$$$) and an integer $$$M$$$ ($$$1 \leq M \leq 10^9+9$$$), compute the remainder of the division of $$$f_{a^b}$$$ by $$$M$$$. In other words, find the unique integer $$$A$$$ such that $$$f_{a^b} - A$$$ is a multiple of $$$M$$$ and $$$0 \leq A \lt M$$$.

Input

The first and only line of input consists of three integers $$$a,b$$$, and $$$M$$$, satisfying $$$1 \leq a,b,M \leq 10^9+9$$$.

Output

Print a single integer: the remainder of the division of $$$f_{a^b}$$$ by $$$M$$$.

Examples
Input
3 2 100
Output
34
Input
2 3 6
Output
3
Input
314159265 271828182 987654321
Output
28908313
Note

In the second test case, note that $$$f_{2^3} = f_8 = 21$$$. The answer is the remainder of the division of $$$21$$$ by $$$6$$$, which is $$$3$$$.