Code Word

Time limit1sMemory limit512 MB

Summary

Count length-l digit sequences on an r by c grid where no two consecutive presses are orthogonally or diagonally adjacent, mod 1e9+7.

Level: Medium5 of 10
Topics: Dynamic programming, Matrix, Combinatorics, Implementation
Solved: No attempts yet

Problem

Following on from the engineering success of Left Pad, Ltd, Lynn started a new venture: Internet of Security, Inc. The company's flagship product will be a device for entering passcodes.

The chief innovation of this device will be in its ability to reject attempts to set insecure passwords. An insecure passcode is defined as a sequence of digit presses such that at least two consecutive presses are either directly or diagonally adjacent.

Lynn, ever-vigilant for the future, is worried that this system might not allow enough unique passcodes to support a large company with trillions of employees. For a given digit pad grid size, and fixed length of password, calculate the number of allowed passwords.

Since the number might be very large in some cases, output your answer mod 1 000 000 007.

Input

The first line contains the integers r and c (1 ≤ r, c ≤ 100), the number of rows and columns of buttons on the pad.
The second line contains the integer l (1 ≤ l ≤ 200), the single allowed length for any passcode.

Output

Output the number of legal passcodes, mod 1 000 000 007.

Examples3

Example 1
Input
```
3 3
2
```
Expected output
```
32
```
Example 2
Input
```
100 1
5
```
Expected output
```
860286658
```
Example 3
Input
```
49 97
191
```
Expected output
```
814099263
```