该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小智正在参与“智汇杯”终极冲刺答题赛。规则如下：

• 试卷共 $n$ 道题目（$1 \leq n \leq 10^7$），需按照顺序作答，每题要么答对（得 $1$ 分），要么答错（成绩清零）。
• 小智的目标是拿到 $m$ 分（$1 \leq m \leq n$），取得胜利；
• 他可以在任意时刻（含开始时）放弃并终止答题，保留当前得分；
• 若答题过程中任意时刻分数达到 $m$ 分，则答题结束并取得胜利（成绩即为 $m$ 分）；
• 现在你知道小智最终取得了 $k$ 分（$0 \leq k \leq m$），请你计算小智可能经历了多少种答题情况，才最终停在 $k$ 分。

输入格式

一行三个整数 $n$、$m$ 和 $k$，用空格隔开。

输出格式

一个整数，表示所有合法答题路径的数量。由于这个整数可能很大，输出该结果对 $10^9+7$ 取模的值。

3 2 1

4

30 10 7

8335366

样例 #1 解释

输入表示共有 3 道试题，答对 2 题即胜利，最终小智得分为 1 分，此时共有 4 种情况：

1. 第一题答对，得分为 1，随后主动终止答题，最终得分为 1；
2. 第一题答错（分数仍为 0），第二题答对，得分由 0 变为 1，随后主动终止答题，最终得分为 1；
3. 第一题答错，第二题答错，第三题答对（此时分数为 1 分），答题结束，最终得分为 1；
4. 第一题答对（得 1 分），第二题答错（分数归零），第三题答对（此时分数为 1 分），答题结束，最终得分为 1。

数据范围

• 对于 60% 的数据，满足：$1 \leq k < m \leq 10$，$10 \leq n \leq 10^6$；
• 对于 100% 的数据，满足：$0 \leq k \leq m$，$1 \leq m \leq n \leq 10^7$。

评测规则

本题采用子任务（Subtask）进行评测，共分为 2 个子任务：

• 子任务 #1（测试点 #1-#15，满分 60 分）：时间限制 1 秒，内存限制 128 MB；
• 子任务 #2（测试点 #16-#25，满分 40 分）：需先通过子任务 #1 所有测试点；时间限制 3 秒，内存限制 256 MB。

为了更好适应不同编程语言的特点，评测端对该题目各语言设置了不同的时间和内存倍率：

• C/C++：1 倍
• Java：2 倍
• Python 3：5 倍

提示

• 答错归零，答题可以随时放弃并终止；
• 当达到 $m$ 分即停止，不能超越；
• 该题数据范围较大，当使用时间复杂度较高的解法时，对于 Java 和 Python 语言，子任务 #2 可能运行时间较长，请耐心等待评测结果回传。