This problem is a programming version of Problem 208 from projecteuler.net
A robot moves in a series of one- circular arcs (), with a free choice of a clockwise or an anticlockwise arc for each step, but no turning on the spot.
For example, one of possible closed paths of arcs with and starting northward is
Given that the robot starts facing North, how many journeys of arcs in length can it take that return it, after the final arc, to its starting position?
Any arc may be traversed multiple times.
Since the answer can be huge, output it modulo .
Input Format
The only line of each test case contains exactly three space-separated integers: , , and .
Constraints
- is a prime number
Output Format
On a single line print the answer modulo .
Sample Input 0
3 6 1000000007
Sample Output 0
8
Explanation 0
If a robot moves in a series of six circular arcs, then there are only journeys that return to the starting position:
Sample Input 1
6 7 1000000009
Sample Output 1
2
Explanation 1
If a robot moves in a series of seven circular arcs, then there are only journeys that return to the starting position:
Sample Input 2
4 8 1000000033
Sample Output 2
18
Explanation 2
If a robot moves in a series of eight circular arcs, then there are journeys that return to the starting position:
