#23 「 数组 」

统计

fabdec有一个长度为n的数组$a[]$(下标1-n),初始时都是0。

fabdec随机了一个1到n的随机数x,并且把a[x]++。

fabdec重复了m次这样的操作,然后数了一下数组里一共有k个位置为奇数。

fabdec现在想问执行m次操作,总共能生成多少种不同的数组使得恰好有k个位置是奇数?(两个数组不同当且仅当两个数组存在某个位置数组的值不相同)

因为这个数字会很大,所以只需输出这个答案除以$10^9+7$的余数。

输入格式

一行三个整数,n,m,k。

输出格式

输出包含一个整数,表示答案。

样例数据

input

2 3 1

output

4

数据规模与约定

$1 \le n,m \le 10^5$, $0 \le k \le n$。

时间限制:1s

空间限制:512MB

Author: zrt