Calculating sums

题号：NC17403
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Niuniu likes calculating sums. He has recently learnt how to calculate sums using various methods. Here is one of them:
$\sum_{i\ =\ 0}^N\ \sum_{j\ =\ 0}^M\ \binom{i}{j}\cdot[i\ \equiv\ 0(mod\ 2)]\cdot[j\ \equiv\ 0(mod\ 2)]$
Note that [x] is 1 when x is true and 0 when x is false.
Can you calculate the sum? The answer may be large, so please calculate the sum modulo a given number K.

输入描述:

The only line contains three integers N, M, K.
1 ≤ N ≤ 10⁹, 1 ≤ M ≤ 10⁶, 1 ≤ K ≤ 10⁹

输出描述:

Print a single line with one number, which is the answer.

示例1

输入

复制

2 3 3

输出

复制