#2004. [HNOI2010] Bus 公交线路

[HNOI2010] Bus 公交线路

题目描述

小 Z 所在的城市有 nn 个公交车站,排列在一条长 (n1) km(n-1)\ \mathrm{km} 的直线上,从左到右依次编号为 11nn,相邻公交车站间的距离均为 1 km1 \ \mathrm{km}

作为公交车线路的规划者,小 Z 调查了市民的需求,决定按下述规则设计线路:

  1. 设共 kk 辆公交车,则 11kk 号站作为始发站,nk+1n-k+1nn 号台作为终点站。
  2. 每个车站必须被一辆且仅一辆公交车经过(始发站和终点站也算被经过)。
  3. 公交车只能从编号较小的站台驶往编号较大的站台。
  4. 一辆公交车经过的相邻两个站台间距离不得超过 p kmp \ \mathrm{km}

在最终设计线路之前,小 Z 想知道有多少种满足要求的方案。由于答案可能很大,你只需求出答案对 3003130031 取模的结果。

输入格式

仅一行包含三个正整数 n,k,pn, k, p,分别表示公交车站数,公交车数,相邻站台的距离限制。

输出格式

仅包含一个整数,表示满足要求的方案数对 3003130031 取模的结果。

10 3 3
1

样例说明 1

可行方案如下:(1,4,7,10),(2,5,8),(3,6,9)(1,4,7,10), (2,5,8), (3,6,9)

5 2 3
3

样例说明 2

可行方案如下:$(1,3,5), (2,4)\quad(1,3,4), (2,5)\quad(1,4), (2,3,5)$。

10 2 4
81

数据规模与约定

对于 100%100\% 的数据,3n1093 \leq n \leq 10^91<p101 < p \leq 101k<min(n1,p,8)1 \leq k < \min(n-1,p,8)