C. Тэгш өнцөгтүүдээр тоглох нь

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Анна Мария хоёр дараах тоглоомоор тогложээ. Эхлээд тэдэнд дөрвөлжин шугамтай цаасан дээр зурагдсан $n × m$ хэмжээтэй тэгш өнцөгт өгөгдөнө. Тэр хоёр ээлжилж нүүх ба Анна эхэлнэ. Нүүдэл бүрд сүүлд зурсан тэгш өнцөгтийн дотор багтах түүнээс жижиг (шугамны дагуу) тэгш өнцөгтийг зурна. Шинээр зурах тэгш өнцөгт нь өмнөх тэгш өнцөгтийг шүргэж болохгүй.

Тоглоомонд хэн нь ч хожихгүй бөгөөд Анна, Мария хоёр зүгээр л нийтдээ $k$ нүүдэл хийж үзжээ. Энэ тоглоомоор нийтдээ хичнээн янзаар тоглож болохыг тоолно уу.

Оролт

Нэг мөрөнд $n$, $m$, $k$ гурван тоо ($1 ≤ n, m, k ≤ 1000$) байрлана.

Гаралт

Нийт боломжит хувилбарын тоо. Энэ тоо маш их байж болох тул $1000000007$-д ($10^9+7$) хуваасан үлдэгдлийг хэвлээрэй.

Орчуулсан: gmunkhbaatarmn

Жишээ тэстүүд

Оролт
3 3 1
Гаралт
1
Оролт
4 4 1
Гаралт
9
Оролт
6 7 2
Гаралт
75

Тэмдэглэл

Тэгш өнцөгтүүдийн зурагдсан байдал яг давхцаж байвал хоёр ижилхэн тоглолт болжээ гэж үзнэ.

Эхний жишээн дээр Анна эхлэн нүүгээд $3 × 3$ нүдэн дотор зурж болох ганц боломжит $1 × 1$ дөрвөлжинг зурна.

Хоёр дахь жишээн дээр Аннад эхний нүүдлээ хийх $9$ боломж байгаа. $1 × 1$ дөрвөлжинг $4$ янзаар. $1 × 2$-г хэмжээтэй тэгш өнцөгтийг босоогоор нь $2$ янзаар, хэвтээгээр нь бас $2$ янзаар, бас $2 × 2$ хэмжээтэйг $1$ янзаар зурж болно.

Сэтгэгдлүүдийг ачааллаж байна...