Oricine a urmărit serialul Star Trek îşi aduce aminte de borgi şi de nava lor spaţială în formă de cub. Una dintre problemele pe care şi-au pus-o înainte de a construi nava a fost următoarea.
Nava borgilor are forma unui paralelipiped dreptunghic de dimensiuni NxMxH, împărţit în camere de dimensiune 1x1x1. Pentru ca nava să poată funcţiona, în aceste camere trebuie plasate K motoare de propulsie, în fiecare cameră putându-se plasa cel mult un motor.
O cameră poate fi identificată printr-un triplet (a, b, c), unde 1 ≤ a ≤ N, 1 ≤ b ≤ M, 1 ≤ c ≤ H, reprezentând coordonatele sale.
Un plan al paralelipipedului este o mulţime de camere de unul dintre următoarele 3 tipuri: {(a, b, c) | a fixat, 1 ≤ b ≤ M, 1 ≤ c ≤ H} – în total sunt N plane de acest tip; {(a, b, c) | b fixat, 1 ≤ a ≤ N, 1 ≤ c ≤ H} – în total sunt M plane de acest tip; {(a, b, c) | c fixat, 1 ≤ a ≤ N, 1 ≤ b ≤ M} – în total sunt H plane de acest tip.
Cerinţă
Se cere să se găsească R, numărul de moduri în care se pot plasa cele K motoare, astfel încât orice plan al paralelipipedului să conţină cel puţin o cameră ocupată de un motor.
Deoarece numărul cerut poate fi foarte mare, este suficient să aflaţi restul împărţirii lui R la 30103.
Date de intrare
Fişierul de intrare borg.in va conţine o singură linie pe care sunt scrise numerele naturale N, M, H, K separate prin câte un spaţiu.
Date de ieşire
Fişierul de ieşire borg.out va conţine o singură linie pe care va fi scris un singur număr natural reprezentând restul împărţirii lui R la 30103.
Restricţii
1 ≤ N, M, H ≤ 20
1 ≤ K ≤ N * M * H
80% dintre teste vor avea K ≤ 2000