Dana je šahovska ploča dimenzije \(n \times m\) i dano je \(k\) topova. Topovi se napadaju ako se nalaze u istom retku ili stupcu. Na koliko načina možete postaviti topove tako da se nijedna dva ne napadaju? Rješenje može biti jako veliko i zato vas molimo da ispišete traženi broj modulo \(10^9 + 7\).

Ulaz

U jedinom retku dana su tri broja \(n\), \(m\) i \(k\) \((1 \leq n \leq 2000, 1 \leq m \leq 10^9, 1 \leq k \leq \min(n,m))\).

Izlaz

U jedinom retku ispišite broj načina na koje možete postaviti sve topove tako da se niti jedna dva ne napadaju, ali modulo \(10^9 + 7\).

U 20% primjera će vrijediti \(n = m = 4\),
U 50% primjera će vrijediti \(1 \leq k \leq n \leq m \leq 300\).

Primjer ulaza

2 2 2

Primjer izlaza

2

Pojašnjenje

Jedina dva načina na koji možemo postaviti dva topa su

T.     .T
.T  ,  T.

Primjer ulaza

3 3 2

Primjer izlaza

18

Primjer ulaza

3 4 2

Primjer izlaza

36