Zadanie

Iste máme dosť hesiel

Počet bodov: 55, časový limit: 1000ms

…ale nie všetky sú dostatočne silné, pomyslel si Adam keď konfiguroval elektronický bezpečnostný systém do T2. Nainštaloval na dvere pin-pad ktorý má \(r\) riadkov po \(s\) stĺpcov gombíkov na vyťukanie hesla. Aby boli heslá v excelovskej textovej databáze pekne zarovnané, aby sa administrátorovi dobre čítali, musia mať všetky dĺžku \(l\).

Ale Adam to už tuší – polovica KSPákov si ako heslo dá samé nuly, a druhá zasa 123456…

Tak to teda nie. Zakázal teda všetky také heslá, v ktorých sú nejaké dve susedné znaky príliš blízko na pin-pade – líšia sa v oboch súradniciach najviac o jedna (teda zakázané znaky tvoria akýsi \(3 \times 3\) štvorček okolo posledného stlačeného tlačítka).

Ale bude platných hesiel dosť? Spočítajte mu to!

Vstup a výstup

V jedinom riadku vstupu sú tri celé čísla \(r\), \(s\) a \(l\) – počet riadkov a stĺpcov pin-padu a požadovaná dĺžka hesla. V prvej sade platí \(1 \leq r,s \leq 3\) a \(1 \leq l \leq 10\). V druhej sade platí \(1 \leq r,s,l \leq 30\). V poslednej sade platí \(1 \leq r,s,l \leq 150\).

Vypočítajte jedno číslo: počet platných hesiel dĺžky \(l\). Keďže toto číslo môže byť obrovské, vypíšte ho modulo \(10^9+7\).

Príklady

Input:

2 3 2

Output:

8

Ak by gombíky v prvom riadku boli a,b,c a v druhm d,e,f, tak platné heslá sú ac, af, dc, df, ea, ed, fa, fd.

Input:

3 3 3

Output:

136