Description

假设有这样一种数列，它满足以下几个条件：

1、每个数都是 0 ~ N - 1 之一；

2、相邻两个数之差绝对值小于等于 k ；

3、至少有一组相邻的数，差的绝对值等于 k ；

4、数列长度为 m 。

现在，给定 n, k, m ，求一共有多少个这样的数列。

Input

少于 10 组测试数据，每组数据一行，三个正整数，n, k, m ，n, k <= 70 ，2 <= m <= 2*10^9。

Output

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

Sample

Input

10 2 2
28 3 3
52 26 4

Output

16
582
240214