Fun Fibonacci#11663

Fun Fibonacci

1 second

128 megabytes

Medium

Find the value of the function

f (x, y) = ⎩ ⎨ ⎧ 0, f (x - 1, y - 2) + f (x - 2, y - 1) + F (x), f (x - 2, y - 2) + F (y), x \leq 0 or y \leq 0 x \leq y x > y

f(x, y) = \begin{cases} 0, & x \le 0~\text{or}~y \le 0 \\ f(x - 1, y - 2) + f(x - 2, y - 1) + F(x), & x \le y \\ f(x - 2, y - 2) + F(y), & x > y \end{cases}

where $F (n)$ is the $n$ -th Fibonacci number, defined as follows:

$F (0) = 2$ F(0) = 2,
$F (1) = 3$ F(1) = 3,
$F (n) = F (n - 1) + F (n - 2)$ F(n) = F(n-1) + F(n-2)

Input

Three integers $x, y, m (0 \leq x, y \leq 500, m \leq 1 0^{9})$ x, y, m~(0 \le x, y \le 500, m \le 10^9).

Output

Print the value of the function $f (x, y) m o d m$ f(x, y)~mod~m.

Examples

Example 1

Loading

f (x, y) = ⎩ ⎨ ⎧ 0, f (x - 1, y - 2) + f (x - 2, y - 1) + F (x), f (x - 2, y - 2) + F (y), x \leq 0 or y \leq 0 x \leq y x > y

F (0) = 2

F (1) = 3

F (n) = F (n - 1) + F (n - 2)

x, y, m (0 \leq x, y \leq 500, m \leq 1 0^{9})

f (x, y) m o d m