- All Contests
- ProjectEuler+
- Project Euler #208: Robot Walks

# Project Euler #208: Robot Walks

# Project Euler #208: Robot Walks

_{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: