1402: #6069. 「2017 山东一轮集训 Day4」塔

Memory Limit:512 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

现在有一条 [1,l] [1, l] [1,l] 的数轴,要在上面造 n n n 座塔,每座塔的坐标要两两不同,且为整点。
塔有编号,且每座塔都有高度,对于编号为 i i i 座塔,其高度为 i i i。对于一座塔,需要满足它与前面以及后面的塔的距离大于等于自身高度(不存在则没有限制)。问有多少建造方案。答案对 m m m 取模。

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

输入格式

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

输出格式

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

样例

样例输入

3 9 17

样例输出

15

数据范围与提示

对于 10% 10\% 10% 的数据,n≤10;l≤25 n \leq 10; l \leq 25 n10;l25
对于 30% 30\% 30% 的数据,n≤20 n \leq 20 n20
对于 50% 50\% 50% 的数据,n≤50 n \leq 50 n50
对于 70% 70\% 70% 的数据,l≤105 l \leq 105 l105
对于 100% 100\% 100% 的数据,n≤100;1≤l≤109;1≤m≤109 n \leq 100; 1 \leq l \leq 10 ^ 9; 1 \leq m \leq 10 ^ 9 n100;1l109;1m109