题目描述

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

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

在房间内部、坐标为整数且互不相同的 $2N$ 个点上，可以放置 $K$ 个障碍物。这些可放置障碍物的位置为：

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

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

任务

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

答案对 $10^9+7$ 取模。

输入格式

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

输出格式

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

数据范围与约定

• $0\le T\le 200$；
• $T$ 是偶数；
• $1\le N\le 100$；
• $0\le K\le 2N$；
• 答案需要对 $10^9+7$ 取模；
• 对 $10\%$ 的测试，$N\le 10$；
• 对 $30\%$ 的测试，$N\le 30$；
• 对 $70\%$ 的测试，$T\le 2N+2$。

样例

输入

6 3 4

输出

7

解释

舞者会在长度为

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

共有 $7$ 种放置方式：

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

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