SPOJ in Armenian

Շախմատի տախտակի վրա հարկավոր է տեղադրել տրված քանակով արքաներ այնպես, որ նրանք իրար չհարվածեն։ Պահանջվում է գրել ծրագիր, որը հաշվի, թե քանի եղանակով է հնարավոր դա անել։ Արքայի հարվածի տակ գտնվում են հորիզոնական, ուղղահայաց և անկյունագծով հարևան վանդակները։

Մուտք

Մուտքում տրված են շախմատի տախտակի  n, m (2 ≤ n,m ≤ 15) չափերը  և արքաների k (1 ≤ k ≤ n*m) քանակը։

Ելք

Ելքում պետք է արտածել մի ամբողջ թիվ, որը ցույց է տալիս, թե n×m շախմատի տախտակի վրա քանի եղանակով է հնարավոր տեղադրել k արքա այնպես, որ նրանք իրար չհարվածեն։ Պատասխանը կարող է մեծ թիվ լինել, բավական է արտածել 1 000 000 007 թվի վրա բաժանելուց մնացորդը։

Օրինակներ

Մուտքը.
4 5 1

Ելքը.
20

Մուտքը.
7 7 16

Ելքը.
1