1441: #6244. 七选五

Memory Limit:256 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

dzm回去学文化课了。

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

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

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

  形式化的讲,就是设集合 S={1,2,...,n}S = \left \{ 1,2,...,n \right \}S={1,2,...,n},标准答案 p1,p2,...,pkp_1, p_2, ..., p_kp1,p2,...,pkSSS 集合选出 kkk 个元素的一个排列。而你要求的即为以 SSS 中的元素组成的排列中,有多少个长度为 kkk 的排列 qqq,满足

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

其中 [pi=qi]\left [ p_i = q_i\right ][pi=qi] 表示若 pi=qip_i = q_ipi=qi 则返回 111 ,否则返回 000

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

输入格式

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

输出格式

  一行一个数,为答案对 109+710^9 + 7109+7 取膜的结果。

样例

样例输入 1

3 2 1

样例输出 1

2

样例解释 1

S={1,2,3}S = \left \{ 1,2,3 \right \}S={1,2,3},答案答案为 1,21,21,2 ,则一共有 1,31,31,33,23,23,2 两种作答得分为 111

样例输入 2

7 5 0

样例输出 2

1214

数据范围与提示

对于前 101010 分的数据, 1≤n≤81 \leq n \leq 81n8 ;
对于中间 505050 分的数据, 1≤n≤20001 \leq n \leq 20001n2000 ;
对于后 404040 分的数据, 1≤n≤1061 \leq n \leq 10^6 1n106 ;
对于 100%100\%100% 的数据, 1≤k≤n≤1061 \leq k \leq n \leq 10^6 1kn1060≤x≤k0 \leq x \leq k0xk

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