Rectangle Coloring

Count the black-or-white colorings of an N by M grid where every X by Y subrectangle contains both colors.

Hard8Dynamic programmingCombinatoricsBit manipulationNo attempts yetTime limit2sMemory limit512 MB

Description

Examples3

Problem

You have an $N \times M$ grid of $1 \times 1$ cells. You color every cell black or white. No rectangle of $X$ rows and $Y$ columns may end up in a single color, so every $X \times Y$ rectangle cut from the grid has to contain at least one black cell and at least one white cell.

Write a program that counts the colorings satisfying this rule.

Input

The first line contains $N$ , $M$ , $X$ , and $Y$ , separated by spaces ( $1 \le X \le 3$ , $2 \le Y \le M$ ).

The ranges of $N$ and $M$ depend on $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$

Output

Print the number of colorings modulo 1,000,000,007 on the first line.