#P17294. [ONTAK 2014] 数字(Liczby)

[ONTAK 2014] 数字(Liczby)

题目描述

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

求满足条件的选法数量,对给定整数 mm 取模。

输入格式

一行三个整数 n,k,mn,k,m:

  • 1≤n,m≤1091\le n,m\le10^9;
  • 0≤k≤1000\le k\le100。

在占 36%36\% 分值的数据中,额外满足 n≤1500n\le1500。

输出格式

输出一个整数,表示合法选法数量对 mm 取模的结果。

样例输入

6 3 1234

样例输出

9