题目描述

dzm 回去学文化课了。

这次英语考试，有一道叫做「七选五」的题。题意是有 $5$ 个空，每个空的答案是给定的 $7$ 个选项之一，即五个空的答案是从 $7$ 个元素选出 $5$ 个元素的一个排列。For example，选项为 $1,2,3,4,5,6,7$，答案可以为 $1,2,3,4,5$。

一个空能得分当且仅当填入该空的选项与答案一致，即你的答案的得分为相同下标元素与标准答案相同的个数。

由于 dzm 之前七选五从来没有错过，所以他认为这一次也不会全错，所以他的答案每一个空也互不相同。但是不幸的是，这一次他一个也没对（迫真）。他想知道，如果这道题变成「$n$ 选 $k$」，那么他按照自己的答题方式（每一个空所填答案互不相同），作答的所有方案得分为 $x$ 的方案数。

形式化的讲，就是设集合 $S = \left \{ 1,2,...,n \right \}$，标准答案 $p_1, p_2, \ldots, p_k$ 为 $S$ 集合选出 $k$ 个元素的一个排列。而你要求的即为以 $S$ 中的元素组成的排列中，有多少个长度为 $k$ 的排列 $q$，满足

$$\left(\sum_{i = 1}^{k}\left [ p_i = q_i\right ]\right) = x$$

其中 $\left [ p_i = q_i\right ]$ 表示若 $p_i = q_i$ 则返回 $1$，否则返回 $0$。

dzm 知道这个答案很大，所以你只需要输出答案对 $10^9 + 7$ 取模的结果。

输入格式

一行三个数，分别为 $n,k,x$。

输出格式

一行一个数，为答案对 $10^9 + 7$ 取模的结果。

样例 1

3 2 1

2

设 $S = \left \{ 1,2,3 \right \}$，答案答案为 $1,2$ ,则一共有 $1,3$ 和 $3,2$ 两种作答得分为 $1$。

7 5 0

1214

数据范围与提示

对于前 $10$ 分的数据， $1 \leq n \leq 8$；
对于中间 $50$ 分的数据， $1 \leq n \leq 2000$；
对于后 $40$ 分的数据， $1 \leq n \leq 10^6$；
对于 $100\%$ 的数据， $1 \leq k \leq n \leq 10^6 ,0 \leq x \leq k$。

本题采用子任务，你需要通过每一部分数据范围所有的数据才能得分。