Code Word
시간 제한1초메모리 제한512 MB
r×c 격자에서 연속한 두 입력이 가로, 세로, 대각선으로 인접하지 않는 길이 l의 암호 개수를 1e9+7로 나눈 나머지를 구한다.
문제
Left Pad, Ltd의 엔지니어링 성공에 이어 Lynn은 새 회사 Internet of Security, Inc.를 세웠다. 이 회사의 주력 제품은 암호를 입력하는 기기이다.
이 기기의 핵심 혁신은 안전하지 않은 비밀번호 설정 시도를 거부하는 기능이다. 안전하지 않은 암호란, 연속으로 누른 두 번의 입력이 가로, 세로, 대각선 중 하나로 인접한 경우가 적어도 한 번 이상 있는 입력열을 말한다.
미래를 항상 경계하는 Lynn은 이 시스템이 수조 명의 직원을 가진 대기업을 지원할 만큼 충분히 많은 고유 암호를 허용하지 않을까 걱정한다. 주어진 숫자 패드 격자 크기와 고정된 비밀번호 길이에 대해, 허용되는 비밀번호의 개수를 계산하라.
어떤 경우에는 그 수가 매우 클 수 있으므로, 답을 1 000 000 007로 나눈 나머지를 출력하라.
입력
- 첫째 줄에는 패드에 있는 버튼의 행과 열 개수 r, c (1 ≤ r, c ≤ 100)가 주어진다.
- 둘째 줄에는 모든 암호에 허용되는 단일 길이 l (1 ≤ l ≤ 200)이 주어진다.
출력
가능한 암호의 개수를 1 000 000 007로 나눈 나머지를 출력하라.