27404번 - Image 서브태스크다국어

Fourier has an image of M × N pixels (M lines, N columns). All the pixels are initially white. Fourier wants to color some pixels in black in order to obtain an amazing image. He considers an image to be amazing if, in any contiguous group of K pixel columns, there exists at least one column containing at least F black pixels.

Fourier is very curious about how many possibilities he has for coloring the image and he asks you to calculate this for him.

The input contains a single line with four integers, M N K F, with the meanings described above.

The output must contain a single integer representing the number of amazing images modulo 1,000,000,007.

• 1 ≤ K ≤ N
• 1 ≤ F ≤ M