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.
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.
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)$$$.
3 3 7
4
5 5 6
3119
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
