Migrated from Lutece 1280 772002画马尾

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

众所周知772002很喜欢马尾，所以他决定画几幅马尾送给他的女朋友。

772002会画$m$种马尾，772002还有$n$张纸，$n$张纸分别编号$1$到$n$，每张纸上只能画一种马尾。

然而772002的女朋友只喜欢其中$t$种马尾。并且772002的女朋友只喜欢偶数（因为这象征着成对成双）。

772002想知道有多少种画法，使得$n$张纸画满并且自己女朋友喜欢的那t种马尾每种个数都恰好为偶数。

然而772002陪女朋友看电影去了，所以他把这个问题交给了你，你能解决吗？

Input

一行，三个整数$m,n,t$。

1-50组数据 $m≤2，t≤m，n≤100$

51-100组数据 $m≤5，t≤m，n≤10000$

101-300组数据 $m≤10，t≤m，n≤1000000000$

Output

一个整数,表示方案数，因为这个数比较大，所以输出对10007求余的结果。

Samples

1 2 0

1

2 93 1

8605

Resources

每周一题 div1