题目描述

从集合 $\{1,2,\ldots,n\}$ 中选出恰好 $k$ 个数，要求所选集合中不能同时出现某个数 $i$ 和它的两倍 $2i$。

求满足条件的选法数量，对给定整数 $m$ 取模。

输入格式

一行三个整数 $n,k,m$：

• $1\le n,m\le10^9$；
• $0\le k\le100$。

在占 $36\%$ 分值的数据中，额外满足 $n\le1500$。

输出格式

输出一个整数，表示合法选法数量对 $m$ 取模的结果。

样例输入

6 3 1234

样例输出

9