시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 5 2 2 40.000%

문제

1×1크기의 칸으로 나누어져 있는 N×M크기의 그리드가 있다. 각각의 칸을 검정색이나 흰색으로 색칠하려고 한다. 이 때, X×Y 크기의 직사각형이 모두 같은 칸으로 색칠되지 않아야 한다.

그리드를 색칠하는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, M, X, Y가 주어진다. (1 ≤ X ≤ 3, 2 ≤ Y ≤ M)

N과 M제한은 X값에 따라서 아래와 같이 달라진다.

  • X = 1인 경우: 2 ≤ N ≤ 1,000,000, 2 ≤ M ≤ 1,000
  • X = 2인 경우: 2 ≤ N ≤ 1,000,000, 2 ≤ M ≤ 7
  • X = 3인 경우: 3 ≤ N ≤ 8, 2 ≤ M ≤ 5

출력

첫째 줄에 경우의 수를 1000000007로 나눈 나머지를 출력한다.

예제 입력

2 2 1 2

예제 출력

4

힌트

출처

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: jh05013