Lonely Lantern Ring
There are lanterns placed at distinct, numbered positions around a ring. Every lantern must be colored either blue or red.
The two neighbors of the lantern at position are the lanterns immediately before and after it around the ring. The numbering wraps around, so the lantern at position is adjacent to the lantern at position .
A lantern is called lonely if both of its neighbors have the other color. For example, a blue lantern is lonely exactly when both neighboring lanterns are red.
Count the color assignments in which exactly lanterns are blue and exactly lanterns are lonely. The positions are labeled: rotations and reflections are considered different assignments unless every position has the same color in both assignments.
Input
The input consists of one line containing three integers , , and (, , and ).
Output
Print one integer: the number of valid color assignments modulo .
Samples
Sample 1
Input
6 3 2
Output
12
There are assignments with exactly blue lanterns and exactly lonely lanterns.
Sample 2
Input
5 2 3
Output
5
There are assignments satisfying the requested color and loneliness counts.
Sample 3
Input
4 4 0
Output
1
The only assignment colors every lantern blue, and none of its lanterns are lonely.