| Fişierul intrare/ieşire: | image.in, image.out | Sursă | ad-hoc |
| Autor | Adăugată de |  Radu Muntean •heracle | |
| Timp execuţie pe test | 30 sec | Limită de memorie | 163840 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Image
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.
Date de intrare
Fişierul image.in contine pe prima linie un numar T, reprezentand numarul de teste. Pe fiecare dintre urmatoarele T liniise afla patru întregi, M N K F, cu semnificaţia de mai sus.
Date de ieşire
Fişierul image.out trebuie să conţină un singur întreg ce reprezintă numărul de imagini uimitoare, modulo 1,000,000,007.
Restricţii
1 ≤ T ≤ 20
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
Exemplu
| image.in | image.out |
|---|---|
| 1 2 6 2 2 | 217 |
| image.in | image.out |
|---|---|
| 1 2 6 2 1 | 3105 |
