题目描述

定义一次“生长”操作如下：对于当前树中的每一个顶点 $x$，新建一个顶点并用一条边将它与 $x$ 相连。

初始时树只有一个顶点。连续执行 $N$ 次生长操作后，树中共有 $2^N$ 个顶点。

在最终得到的树中，统计长度恰好为 $D$ 的简单路径数量，并对质数 $P$ 取模。

一条简单路径的长度定义为路径包含的边数。若两条路径包含的边集合不同，则视为不同；同一条路径正向和反向遍历不重复计数。

输入格式

一行输入三个整数 $N,D,P$。

输出格式

输出长度恰好为 $D$ 的简单路径数量对 $P$ 取模后的结果。

数据范围

• $1\le N\le10^9$；
• $1\le D\le500$；
• $503\le P\le1\,000\,000\,009$；
• $P$ 为质数。

样例

3 3 1000000007

8