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

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

입력 형식

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

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