dzm回去学文化课了。

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

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

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

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

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

其中 [pi=qi] 表示若 p_i = q_i 则返回 1 ,否则返回 0 。

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

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

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

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

LOJ