#描述#
假设有这样一种数列，它满足以下几个条件：
<BR>
1、每个数都是 0 ~ N - 1 之一；
<BR>
2、相邻两个数之差绝对值小于等于 k ；
<BR>
3、至少有一组相邻的数，差的绝对值等于 k ；
<BR>
4、数列长度为 m 。
<BR>
现在，给定 n, k, m ，求一共有多少个这样的数列。

#格式#
##输入格式##
少于 10 组测试数据，每组数据一行，三个正整数，n, k, m ，n, k &lt= 70 ，2 &lt= m &lt= 2*10^9。

##输出格式##
由于数据比较大，输出答案对 1000000007 的模。

#样例1#
##样例输入1##

10 2 2
28 3 3
52 26 4

##样例输出1##

16
582
240214

#限制#
5000ms
32768KB

#提示#

#来源#