#PQJ2877x16278. QOJ 2877_16278
QOJ 2877_16278
小 Z 所在的城市有 𝑁 个公交车站,排列在一条长为 𝑁 − 1 公里的直线上,从左到右依次编号为 1 到 𝑁 ,相邻公交车站间的距离均为 1 公里。
作为公交车线路的规划者,小 Z 调查了市民的需求,决定按以下规则设计线路:
设共有 𝐾 辆公交车,则 1 到 𝐾 号车站作为始发站, 𝑁 − 𝐾 + 1 到 𝑁 号车站作为终点站。 每个车站必须被一辆且仅一辆公交车经停(始发站和终点站也算被经停)。 公交车只能从编号较小的车站驶向编号较大的车站。 一辆公交车经停的相邻两个车站间的距离不得超过 𝑃 公里。
注意“经停”是指经过并停车,因经过不一定会停车,故经停与经过是两个不同的概念。
在最终确定线路之前,小 Z 想知道有多少种满足要求的方案。由于答案可能很大,你只需求出答案对 30031 取模的结果。
输入格式
输入只有一行,其中包含用空格隔开的三个正整数 𝑁 , 𝐾 , 𝑃 ,分别表示公交车站数、公交车数、一辆公交车经停的相邻两个车站间的最大距离。
输入的数据保证 40 % 的数据满足 𝑁 ≤ 1000 。 100 % 的数据满足 1 < 𝑁 < 10 9 , 1 < 𝑃 ≤ 10 , 𝐾 < 𝑁 , 1 < 𝐾 ≤ 𝑃 。
输出格式
仅包含一个整数,表示满足要求的方案数对 30031 取模的结果。
样例数据 样例 1 输入 10 3 3 样例 1 输出 1 样例 2 输入 5 2 3 样例 2 输出 3 样例 3 输入 10 2 4 样例 3 输出 81 样例解释
样例一满足要求的方案只有 1 种,即: ( 1 , 4 , 7 , 10 ) , ( 2 , 5 , 8 ) , ( 3 , 6 , 9 ) 。
样例二满足要求的方案有 3 种,即: ( 1 , 3 , 5 ) , ( 2 , 4 ) ; ( 1 , 3 , 4 ) , ( 2 , 5 ) 和 ( 1 , 4 ) , ( 2 , 3 , 5 ) 。