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

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

题目描述

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

输入格式

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

输出格式

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

3 9 17
15

数据范围与提示

对于 10%10\% 的数据,n≤10;l≤25n \leq 10; l \leq 25;
对于 30%30\% 的数据,n≤20n \leq 20;
对于 50%50\% 的数据,n≤50n \leq 50;
对于 70%70\% 的数据,l≤105l \leq 105;
对于 100%100\% 的数据,n≤100;1≤l≤109;1≤m≤109n \leq 100; 1 \leq l \leq 10 ^ 9; 1 \leq m \leq 10 ^ 9。