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 şi 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 şi precizări

• 1 ≤ N, M, H ≤ 20
• 1 ≤ K ≤ N * M * H
• 80% din teste vor avea K ≤ 2000

Exemple

borg.in

3 1 2 4

borg.out

12

borg.in

3 1 2 2

borg.out

0