문제 설명
텔레토비 동산(이하 텔동)을 좋아하는 대승이는 가을을 맞아 텔동에 나들이를 나왔습니다.
대승이는 나들이 중 문득 텔동을 벗어나게 되는 경우의 수가 궁금해졌습니다.
대승이가 나들이에 집중 할 수 있도록 여러분이 대승이를 대신하여 경우의 수를 구해주세요.
텔동은 격자모양이며 M x N의 크기이고, 대승이는 상하좌우 4방향으로 최대 K걸음까지 걸을 수 있습니다.
시작위치 r과, c로부터 K걸음 이내로 움직였을 때 텔동의 경계 밖으로 벗어나게 되는 경우의 수를 구해주세요.
(그런데 텔동을 한 번 나간경우 흥이 깨져서 다시 들어올 수 없습니다.)
대승이는 나들이 중 문득 텔동을 벗어나게 되는 경우의 수가 궁금해졌습니다.
대승이가 나들이에 집중 할 수 있도록 여러분이 대승이를 대신하여 경우의 수를 구해주세요.
텔동은 격자모양이며 M x N의 크기이고, 대승이는 상하좌우 4방향으로 최대 K걸음까지 걸을 수 있습니다.
시작위치 r과, c로부터 K걸음 이내로 움직였을 때 텔동의 경계 밖으로 벗어나게 되는 경우의 수를 구해주세요.
(그런데 텔동을 한 번 나간경우 흥이 깨져서 다시 들어올 수 없습니다.)
입력 설명
첫째 줄에는 최대 걸음 수 K (0 ≤ K ≤ 50)가 주어집니다.
둘째 줄에는 텔동의 크기 M, N (1 ≤ M, N ≤ 50)이 주어집니다.
셋째 줄에는 대승이의 시작위치 r (0 ≤ r < M), c (0 ≤ c < N)가 주어집니다.
둘째 줄에는 텔동의 크기 M, N (1 ≤ M, N ≤ 50)이 주어집니다.
셋째 줄에는 대승이의 시작위치 r (0 ≤ r < M), c (0 ≤ c < N)가 주어집니다.
출력 설명
텔동의 경계 밖으로 벗어나게 되는 경우의 수를 구해주세요.
단, 너무 큰 숫자가 나올 수 있으니 결과값을 1,000,000,007 로 나눈 나머지를 출력해주세요.
단, 너무 큰 숫자가 나올 수 있으니 결과값을 1,000,000,007 로 나눈 나머지를 출력해주세요.
입력 예시 Copy
3
1 2
0 1
출력 예시 Copy
9
도움
예시에 나온 상황은 아래와 같이 9가지 경우의 수가 존재합니다.
