직사각형 색칠

$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로 나눈 나머지를 출력한다.