B. Shooting
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Igor and Ira decided to determine the head of the family, for this they will hold an archery tournament. The tournament is held according to simple rules: each of the participants shoots $$$n$$$ times (the first participant makes all his shots, then the second). Target — a circle consisting of $$$k$$$ rings, $$$1$$$ to $$$k$$$ points are given for hitting each of them. The head of the family is the one who scores more points.

Igor has already made his $$$n$$$ shots and scored $$$p$$$ points. Now it's Ira's turn. She has already adapted to archery, and now she always hits the target, unlike Igor. Ira hits each ring with the same probability.

Help Ira determine the number of winning combinations from $$$n$$$ shots.

Input

A single line contains three integers $$$n$$$, $$$k$$$, $$$p$$$ $$$(1\leq n, k\leq 300, 0 \le p\leq k\cdot n)$$$ — the number of shots, the number of rings on the target, and the number of points scored by Igor.

Output

In a single line print a number — the number of combinations of $$$n$$$ Ira's shots at the target, such that the sum of points scored will be greater than $$$p$$$.

Output the answer modulo 1000000007$$$(10^9+7)$$$.

Examples
Input
3 3 7
Output
4
Input
5 5 6
Output
3119
Note

In the first test, there are the following combinations of Ira hitting the target, in which Ira scores more points than Igor.

$$$[2,3,3]$$$ total points: 8

$$$[3,2,3]$$$ total points: 8

$$$[3,3,2]$$$ total points: 8

$$$[3,3,3]$$$ total points: 9