직사각형 색칠

N x M 격자를 흑백으로 칠할 때 모든 X x Y 부분 직사각형이 두 색을 모두 포함하도록 하는 색칠의 수를 세는 문제이다.

어려움8동적 계획법조합론비트 연산아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제 설명

예제3

문제

$1 \times 1$ 크기의 칸으로 나누어진 $N \times M$ 격자가 있다. 각 칸을 검은색이나 흰색으로 칠하려고 한다. 이때 세로 $X$ 칸, 가로 $Y$ 칸짜리 직사각형이 한 가지 색으로만 칠해지면 안 된다. 즉 격자에서 잘라낸 모든 $X \times Y$ 직사각형은 검은 칸과 흰 칸을 적어도 하나씩 포함해야 한다.

조건을 만족하는 색칠 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 $N$ , $M$ , $X$ , $Y$ 가 공백으로 구분되어 주어진다. ( $1 \le X \le 3$ , $2 \le Y \le M$ )

$N$ 과 $M$ 의 범위는 $X$ 에 따라 달라진다.

$X = 1$ 인 경우: $2 \le N \le 1{,}000{,}000$ , $2 \le M \le 1{,}000$
$X = 2$ 인 경우: $2 \le N \le 1{,}000{,}000$ , $2 \le M \le 7$
$X = 3$ 인 경우: $3 \le N \le 8$ , $2 \le M \le 5$

출력

첫째 줄에 색칠 방법의 수를 1,000,000,007로 나눈 나머지를 출력한다.