# Gostilna

Gustav, lastnik starodavne gostilne ob vaški cerkvi, že dolgo časa nevoščljivo opazuje trume, ki se vsako nedeljo zgrinjajo v sosednjo stavbo, medtem ko mora sam zaradi protikoronskih ukrepov še vedno imeti zaprta vrata. No, po zadnjih vesteh naj bi jih vendarle lahko odprl, a le pod pogojem, da noben par gostov ne sedi na medsebojni razdalji, manjši od 2. Na koliko načinov lahko izpolni ta pogoj pri $N$ gostih, če so njegove mize razporejene v kvadratni mreži s $H$ vrsticami in $W$ stolpci, razdalja med sosednjima mizama v isti vrstici ali stolpcu pa znaša 1?

## Vhod

Na standardnem vhodu je zapisana ena sama vrstica, ta pa vsebuje števila $H$, $W$ in $N$.

## Izhod

Na standardni izhod izpiši iskano število načinov po modulu $(10^9 + 7)$.

## Podnaloge

Za vse testne primere velja:

- $1 \le H \le 10$;
- $1 \le W \le 1000$;
- $1 \le N \le 10$.

1. podnaloga (10 točk): $N \le 2$.
2. podnaloga (15 točk): $H = 1$, $W \le 10$.
3. podnaloga (25 točk): $H = 1$.
4. podnaloga (20 točk): $H \le 6$, $W \le 6$.
5. podnaloga (30 točk): Ni dodatnih omejitev.

## Primer

### Vhod

2 5 3

### Izhod

8

### Komentar

V tem primeru imamo sledeče možne razporeditve: