神-原
题号：NC262154
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

神原 , 起...啊不对串台了。

博德之门 , 启动!

然而 size(Baldur's Gate 3) > size(Your Data Usage Limit)，所以你只能通过做下面这道题来泄愤。

如果集合 S 的最小整数等于它的大小 ，称集合 S 为完美的（空集不是完美集合） , 即 \min\{x : x \in S\} = |S|。

记 P(S) 为集合 S 中所有完美子集的数量。

现给定一个质数 p，以及一集合 S = \{ 1 , 2, \cdots, n \}，你需要从 S 中删除 m 个数 , 得到 S'。

问 P(S') 的最小值是多少 , 结果模 p。

输入描述:

第一行三个整数 n，m，p。

1 \leq n \leq 10^9

0 \leq m \leq 10^9

2 \leq p \leq 10^6

保证 m \leq n

输出描述:

一行一个整数 , P(S')\ \mathrm{mod} \ p 。
示例1

输入

复制 
30 0 5

输出

复制 
0

说明

832040 % 5 = 0
示例2

输入

复制 
19260 8 17

输出

复制 
6