Ancient Civilization's Road Network

An ancient civilization had n cities numbered from 1 to n. In its prime, the civilization built exactly m roads among the cities. However, the roads were built with two unique constraints:

1. The civilization worshipped the number k. Hence, for any road connecting cities u and v, it is required that \(1 \le |u-v| \le k\).
2. Every city is connected to an even number of roads (note that 0 is considered even).

Two road networks are considered different if there exists at least one pair of cities for which the number of connecting roads differs. Note that the network does not have to be connected.

Given integers n, m, and k, determine the number of possible road networks modulo \(10^9+7\).

inputFormat

The input consists of a single line containing three integers n, m, and k where:

• n is the number of cities.
• m is the total number of roads.
• k is the parameter that restricts a road connecting cities u and v to satisfy \(1 \le |u-v| \le k\).

outputFormat

Output a single integer, which is the number of possible road networks that satisfy the above conditions modulo \(10^9+7\).

sample

2 1 1

0