#P5270. 打隔膜

打隔膜

打隔膜

题目描述

长度为 nn 的铁轨包含编号 1,2,…,n1,2,\ldots,n 的整数位置。 在其中互不相同的 kk 个位置各放置一辆火车。 从左向右,火车依次属于YJC、大火车、YJC、大火车,二人各有 k/2k/2 辆。

YJC先手,双方轮流操作。每次选择自己至少1辆、至多 mm 辆火车, 每辆所选火车各移动一个正整数距离,不同火车可以移动不同距离。

  • YJC的火车只能向右移动;大火车的火车只能向左移动。
  • 移动后仍须位于 1,…,n1,\ldots,n,全部火车的原左右次序必须严格保持。
  • 火车不能重合或穿越其他火车。

无法进行合法操作的一方输。双方都采用最优策略。 求使YJC必胜的初始布局数,答案对 109+710^9+7 取模。 不同布局指占据的位置集合不同;火车归属由从左向右的次序唯一确定。

输入格式

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

输出格式

输出一行一个整数,表示答案。

样例

3 2 1
1

数据范围

kk 为偶数,1≤m≤k≤n≤100001\le m\le k\le n\le10000,k≤1000k\le1000。