- Prepare
- Functional Programming
- Memoization and DP
- Sherlock and the Maze

# Sherlock and the Maze

# Sherlock and the Maze

Watson gives a 2-D grid to Sherlock. Rows are numbered *1* to *N* from top to bottom and columns are numbered *1* to *M* from left to right. Sherlock is at position *(1,1)* right now and he is free to face any direction before he starts to move. He needs to reach *(N,M)*. In one step, he can either move downwards or rightwards. Also, he cannot make more than *K* turns during his whole journey.

There are two possible scenarios when a turn can occur at point *(i, j)*:

```
Turns Right: (i-1, j) -> (i, j) -> (i, j+1)
Down Right
Turns Down: (i, j-1) -> (i, j) -> (i+1, j)
Right Dowm
```

Given *N*, *M* and *K*, help him by printing the number of ways to reach *(N,M)* with at most *K* turns. As this value can be very large, print the answer modulo (10^{9} + 7).

**Input**

First line contains *T*, the number of testcases. Then *T* lines follow, where each line represents a test case. Each testcase consists of three space separated integers, *N M K*, where *(N, M)* is the final location and *K* is the maximum number of allowed turns.

**Output**

For each testcase, print the required answer in one line.

**Constraints**

1 ≤ *T* ≤ 10

1 ≤ *N, M* ≤ 100

0 ≤ *K* ≤ 100

**Note**

- He can take
**at most***K*turns. - He is free to face any direction before starting from
*(1, 1)*.

**Sample Input**

```
3
2 2 3
2 3 1
4 4 4
```

**Sample Output**

```
2
2
18
```

**Sample explanation**

*Test Case #00:* There is no way to reach *(2, 2)* with 0, 2 or 3 turns. He will always reach *(2, 2)* with 1 turn only. There are two ways shown below:

- He starts from
*(1, 1)*facing right and moves to*(1, 2)*. Then he faces down and moves to*(2, 2)*. - He starts from
*(1, 1)*facing down and moves to*(2, 1)*. Then he turns right and moves to*(2, 2)*.

*Test Case #01:* He can't reach *(2, 3)* with 0 turns. There are only two ways to reach *(2, 3)* with exactly 1 turn.

- He starts from
*(1, 1)*facing down and moves to*(2, 1)*. Then he turns right and takes two steps forward to reach*(2, 3)*. - He starts from
*(1, 1)*facing right and moves two steps forward to reach*(1, 3)*. Then he turns down and proceeds one step to*(2, 3)*.

*Test Case #02:* There are 0 ways with 0 turn, 2 ways with 1 turn, 4 ways with 2 turns, 8 ways with 3 turns and 4 ways with 4 turns to reach *(4, 4)*.

**Tested by:** Ashutosh Singla, Abhiranjan