题目描述

小K很无聊，对于集合 $ T=\{a_1,a_2,\dots,a_{n-1},a_n\}(a_1\ge a_2\ge\dots\ge a_{n-1}\ge a_n) $ ，定义权值 $P(T)=\sum_{i=1}^n a_i\times (-1)^{i-1}$ 。

又定义 $S_1(T)=P(T)$， $S_i(T)=\sum_{R\in T}S_{i-1}(R)$ 。

给定 $n,m,p$，他想知道 $S_n(\{m,m-1,m-2,\dots,2,1\})\mod p$。

输入

一行 $n,m,p$ 三个数。

输出

一个整数 $S_n(\{m,m-1,m-2,\dots,2,1\})\mod p$。

样例

2 3 998244353

12

1 66666 100000007

33333

48324 98323 100000007

73978329

数据范围

$1\le n,m\le 10^5,10^8\le p\le 10^9,p$ 为质数。