SOLVE
LATER
Rhezo is the new manager of Specialist Cinema Hall. A new movie is being released this Friday and Rhezo wants people in the hall to be seated according to some rules. His rules are weird and he likes that no 2 people in a row sit together/adjacent. He also wants that there are at least 2 people in each row.
The hall should have at least K people in it, if there are less the show gets cancelled. The hall can be visualised as a \(N \times M\) matrix. Rhezo wants to find the number of different seating arrangements of people in it. Two seating arrangements are different if there is at least one seat which is filled in one arrangement and vacant in other.
You being Rhezo's best friend, want to help him in this task. As the number can be large, output your answer modulo \(10^9+7\).
Input:
First line of input contains 2 integers N and M. Second line contains a single integer K.
Output:
Find the number of different arrangements of people in the hall satisfying the constraints given in problem statement. Output your answer modulo \(10^9+7\).
Constraints:
\(1 \le N, K \le 500\)
\(1 \le M \le 10\)
Following are the 7 different seating arrangements:
x.x.x
..x.x
.x..x
.x.x.
x...x
x..x.
x.x..