Informatica Online Judge

  GS폰의 잠금 패턴 [1613 / 064D]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 49   Total Tried : 62


The Champion of this Problem (C++) : gs18121 - ms / 585byte
My Best Submission (C++) : N/A

[JKJeong 2016]

Background

경곽이는 이번에 GS폰을 개발했다.

이 폰의 초기화면 잠금은 n행 m열로 이루어진 점들 중 하나에서 출발하여 길이가 l인 패턴으로 구성된다.

한 번의 연결은 현재 지점에서 상, 하, 좌, 우, 대각선으로 인접한 지점으로만 연결할 수 있다.

이 때, 같은 점을 여러 번 거쳐도 되며, 패턴의 모양이 교차되어도 상관 없다. 즉 마음대로 패턴을 정할 수 있다.

n, m, l이 주어질 때, 가능한 패턴의 모든 경우의 수를 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 n, m, l이 공백으로 구분되어 입력된다.

[입력값의 정의역]
1 <= n, m <= 10
1 <= l <= 1,000

Output

만들 수 있는 패턴의 수를 출력한다.
단, 수가 너무 커질 수 있으므로 100,000,007로 나눈 나머지를 출력한다.

IO Example

입력
2 2 1

출력
12

설명 : 다음과 같이 12가지가 있다.
(1, 1) - (1, 2)
(1, 1) - (2, 1)
(1, 1) - (2, 2)
(2, 1) - (1, 1)
(2, 1) - (1, 2)
(2, 1) - (2, 2)
(1, 2) - (2, 1)
(1, 2) - (1, 1)
(1, 2) - (2, 2)
(2, 2) - (1, 1)
(2, 2) - (1, 2)
(2, 2) - (2, 1)

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]