시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 0 0 0 0.000%

문제

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.

입력

  • 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 the number of legal passcodes, mod 1 000 000 007.

예제 입력 1

3 3
2

예제 출력 1

32

예제 입력 2

100 1
5

예제 출력 2

860286658

예제 입력 3

49 97
191

예제 출력 3

814099263