Rhezo and Cinema Hall
Tag(s):

## Combinatorics, Data Structures, Dynamic Programming, Easy-Medium

Problem
Editorial
Analytics

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$

SAMPLE INPUT
1 5 2
SAMPLE OUTPUT
7

Explanation

Following are the 7 different seating arrangements:

x.x.x

..x.x

.x..x

.x.x.

x...x

x..x.

x.x..

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

International Women's Hackathon

OTHER PROBLEMS OF THIS CHALLENGE
• Data Structures > Arrays