题目描述

又到了小 H 被强迫背单词的时间了！

英语老师要求小 H 在一秒之内背下一本《考纲词汇 3500》中的 $N(2 \leq N \leq 3500)$ 个单词，这无疑是一场折磨。

但是经验丰富的小 H 完全没有表现出一点怯色，他事不关己地说道：

“我可是有超强记忆法的男人！”

小 H 的超强记忆法是，从这 $N$ 个单词中选出 $i$ 个互不相同的单词凑成一句完全不 通顺的话，他坚信自己能将其背下。(注意 $i$ 可以为 $0$)。 为了加深每个单词的印象，他不仅要凑出许多互不相同的句子，还必须保证每个单词在这些句子里的总出现次数大于等于 $k$ 次。 为了显示自己的强大，他想知道自己有多少种取胜的拼凑方案。 当然，小 H 的思维惊为天人，他只需要你算出方案数对质数 $M$ 取模的结果。

简要题意

对于一个大小为 $N$ 的集合 ${1, 2, . . . , N}$，求“它的子集组成的集合”的子集中，有 多少个满足 $1, 2, . . . , N$ 均出现了至少 $k$ 次，答案对 $M$ 取模。

输入格式

从文件 recite.in 中读入数据。 一行三个整数 $N, M, k$。

输出格式

输出到文件 recite.out 中。 一行一个整数，表示能选出的方案数 $ans$ 对 $M$ 取模的结果

样例输入 1

2 1000000007 2

样例输出 1

2

样例输入 2

3 147744151 1

样例输出 2

218

对于 $100 \%$ 的数据，$2 \leq n \leq 3500, k = {0, 1, 2}, 10^8 ≤ M ≤ 10^9 + 9$ 且 $M$ 为质数。