Koniec kola: 1. február 2021 23:59
7 dní
Počet bodov:
Popis:  12b
Program:  8b

Blíži sa jar, kvety začnú pučať, hady sa začnú hadiť. Každý čo i len trochu decentný hadonoš si teraz plánuje rozloženie svojej zbierky na hadisko. Počet možných rozložení je častokrát obrovský, avšak mnoho začínajúcich hadonošov si to vôbec neuvedomuje a príprave nevenujú dostatok času. Navyše sa potom čudujú, keď dosiahnu malý hadiaci kvocient a v lete slabú úrodu! Pre mnohých z vás je toto tiež iba prvá hadonošská jar, a povedzme si to na rovinu, vieme, že nie všetci ste z tých najzodpovednejších. Možno by ste to brali serióznejšie, keby ste presne vedeli ako hrozne veľa kombinácii treba zvážiť? Dokonca to možno poslúži ako dobrá rozcvička vašich mozgov pred tým, ako sa začnete trápiť s hľadaním toho optimálneho rozloženia.

Úloha

Hadisko má tvar mriežky s rozmermi \(N \times M\). Vo vašej zbierke je \(K\) hadov a radi by ste ich rozložili na hadisko. Na každé políčko môžete položiť najviac jedného hada, a aby sa príliš nepohadili, do každého stĺpca a riadku nanajvýš dvoch. Pre účely hadenia môžeme všetkých hadov aj napriek ich náramne odlišným osobnostiam považovať za identických. Koľko existuje rôznych rozložení? Keďže ich môže byť ale že naozaj veľa, ako odpoveď uvádzajte výsledok modulo \(10^9+7\).

Formát vstupu

Na jedinom riadku su tri celé čísla \(N\), \(M\), \(K\) – rozmery hadiska a počet hadov.

Formát výstupu

Na výstup vypíšte koľko existuje rôznych rozložení modulo \(10^9+7\).

Obmedzenia

Vstupy budú rozdelené do 4 sád. Každá sada bude hodnotená 2 bodmi. Platia v nich nasledujúce obmedzenia:

Sada 1 2 3 4
\(1 \leq N,M \leq\) \(5\) \(20\) \(50\) \(100\)
\(0 \leq K \leq\) \(5\) \(10\) \(100\) \(200\)

Príklady

Input:

1 1 1

Output:

1

Input:

2 2 2

Output:

6

Input:

3 3 3

Output:

78

Input:

4 4 4

Output:

1428

Input:

5 5 5

Output:

34020

Odovzdávanie

Na odovzdávanie sa musíš prihlásiť

Otázky a diskusia

Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.