#P16026. [Lot2017]Piruete

[Lot2017]Piruete

题目描述

给定一个自然数 NN,有一个长度为 2N+22N+2 的房间,可以看作闭区间

[−N−1,N+1].[-N-1,N+1].

房间中心为 C=0C=0。一位名叫 Costelina Salopeta 的芭蕾舞者最初站在 CC 点。她将完成 TT 步舞蹈,每一步长度为 11,并且第一步向右走。

在房间内部、坐标为整数且互不相同的 2N2N 个点上,可以放置 KK 个障碍物。这些可放置障碍物的位置为:

−N,−N+1,…,−1,1,2,…,N.-N,-N+1,\ldots,-1,1,2,\ldots,N.

当芭蕾舞者到达一个有障碍物的点时,她会被绊倒并做一个旋转,因此改变移动方向,同时该位置上的障碍物会消失。

不能在坐标 −N−1-N-1、00、N+1N+1 上放置普通障碍物。坐标 −N−1-N-1 与 N+1N+1 处的墙壁视为永久障碍物,碰到后不会消失;坐标 00 是舞者初始位置。

任务

给定 T,N,KT,N,K,计算有多少种放置这 KK 个障碍物的方式,使得舞者完整走完 TT 步之后,回到起点 C=0C=0。

答案对 109+710^9+7 取模。

输入格式

第一行包含三个自然数 T,N,KT,N,K,含义如题所述。

输出格式

第一行包含一个自然数,表示答案对 109+710^9+7 取模后的结果。

数据范围与约定

  • 0≤T≤2000\le T\le 200;
  • TT 是偶数;
  • 1≤N≤1001\le N\le 100;
  • 0≤K≤2N0\le K\le 2N;
  • 答案需要对 109+710^9+7 取模;
  • 对 10%10\% 的测试,N≤10N\le 10;
  • 对 30%30\% 的测试,N≤30N\le 30;
  • 对 70%70\% 的测试,T≤2N+2T\le 2N+2。

样例

输入

6 3 4

输出

7

解释

舞者会在长度为

2N+2=2⋅3+2=82N+2=2\cdot3+2=8

的房间中完成 T=6T=6 步,并放置 K=4K=4 个障碍物。

共有 77 种放置方式:

1. [.x.Cxxx]
2. [.xxC.xx]
3. [x.xC.xx]
4. [xx.Cx.x]
5. [xx.Cxx.]
6. [xxxC.x.]
7. [xxxC..x]

其中 . 表示空位置,x 表示障碍物。