「2017 山东一轮集训 Day4」塔

传统 1000 ms 512 MiB

$170$ 通过 $370$ 提交

题目描述

现在有一条 $[1, l]$ 的数轴，要在上面造 $n$ 座塔，每座塔的坐标要两两不同，且为整点。

塔有编号，且每座塔都有高度，对于编号为 $i$ 座塔，其高度为 $i$。对于一座塔，需要满足它与前面以及后面的塔的距离大于等于自身高度（不存在则没有限制）。问有多少建造方案。答案对 $m$ 取模。

塔不要求按编号为顺序建造。

输入格式

一行三个整数 $n, l, m$。

输出格式

输出一个整数，代表答案对 $m$ 取模的值。

样例

输入

3 9 17

输出

15

数据范围与提示

对于 $10\%$ 的数据，$n \leq 10$； $l \leq 25$；
对于 $30\%$ 的数据，$n \leq 20$；
对于 $50\%$ 的数据，$n \leq 50$；
对于 $70\%$ 的数据，$l \leq 10^5$；
对于 $100\%$ 的数据，$n \leq 100$； $1 \leq l \leq 10^9$； $1 \leq m \leq 10^9$。