Amazing Images

Interview

Time limit0.6sMemory limit1024 MB

Summary

Count the colorings of an M by N pixel grid where every K consecutive columns include a column with at least F black pixels, modulo 1,000,000,007.

Level: Medium5 of 10
Topics: Dynamic programming, Prefix sum, Combinatorics
Solved: No attempts yet

Problem

Fourier has an image of $M \times N$ pixels ( $M$ lines, $N$ columns). All the pixels are initially white. Fourier wants to color some pixels black to obtain an amazing image. He considers an image amazing if, in every contiguous group of $K$ pixel columns, at least one column contains at least $F$ black pixels.

Fourier wants to know how many ways he can color the image, and he asks you to compute this count.

Input

The input contains a single line with four integers $M$ , $N$ , $K$ , and $F$ , in that order.

Output

Print a single integer, the number of amazing images modulo 1,000,000,007.

Constraints

$1 \le K \le N$

$1 \le F \le M$

Examples2

Example 1
Input
```
2 6 2 2
```
Expected output
```
217
```
Example 2
Input
```
2 6 2 1
```
Expected output
```
3105
```