== include(page="template/taskheader" task_id="image") ==

Poveste şi cerinţă...

 
Fourier are o imagine cu M × N pixeli (M linii, N coloane). Toţi pixelii sunt iniţial albi. Fourier doreşte să coloreze anumiţi pixeli în negru pentru a obţine o imagine uimitoare. El consideră că o imagine este uimitoare dacă, în orice grup continuu de K coloane există cel puţin o coloană care conţine cel puţin F pixeli negri.
 
Fourier este foarte curios să afle câte posibilităţi are pentru a colora imaginea şi te roagă să calculezi această valoare.

h2. Date de intrare

Fişierul de intrare $image.in$ ...

 
Fişierul $image.in$ are o singură linie cu patru întregi, M N K F, cu semnificaţia de mai sus.

h2. Date de ieşire

În fişierul de ieşire $image.out$ ...

Fişierul $image.out$ trebuie să conţină un singur întreg ce reprezintă numărul de imagini uimitoare, modulo 1,000,000,007.

h2. Restricţii

* $... ≤ ... ≤ ...$

1 ≤ K ≤ N
1 ≤ F ≤ M
Limita de timp: 0.6 secunde
Limita de memorie: 256 MB
 
 
pentru 10 puncte
M × N ≤ 20
 
pentru alte 20 de puncte
N × K ≤ 70,000,000
M ≤ 20
 
pentru alte 30 de puncte
N ≤ 10,000,000
M ≤ 20
 
pentru alte 40 de puncte
N ≤ 1,000,000,000
K ≤ 100
M ≤ 20
 

h2. Exemplu
table(example). |_. image.in |_. image.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 2 6 2 2
| 217

|

h3. Explicaţie
 
...

table(example). |_. image.in |_. image.out |
| 2 6 2 1
| 3105
|

== include(page="template/taskfooter" task_id="image") ==