#P3204. [HNOI2010] 公交线路

[HNOI2010] 公交线路

题目描述

小 Z 所在的城市有 NN 个公交车站,排列在一条长 (N1) km(N-1)\ \rm km 的直线上,从左到右依次编号为 11NN,相邻公交车站间的距离均为 1 km1 \ \rm km。作为公交车线路的规划者,小 Z 调查了市民的需求,决定按下述规则设计线路:

  1. 设共 KK 辆公交车,则 11KK 号站作为始发站,NK+1N-K+1NN 号台作为终点站。
  2. 每个车站必须被一辆且仅一辆公交车经过(始发站和终点站也算被经过)。
  3. 公交车只能从编号较小的站台驶往编号较大的站台。
  4. 一辆公交车经过的相邻两个站台间距离不得超过 P kmP \ \rm km

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

输入格式

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

输出格式

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

10 3 3
1
5 2 3
3
10 2 4
81

提示

【样例说明】

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

样例二的可行方案如下:(1,3,5)(1,3,5)(2,4)(1,3,4)(2,4)(1,3,4)(2,5)(1,4)(2,5)(1,4)(2,3,5)(2,3,5)

对于 100%100 \% 的数据,1N1091 \le N \le 10^91<P101 < P \le 10K<NK<N1<KP1<K \le P