A. Тэгш өнцөгтийн тоглоом

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

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

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

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

Анна Мариа 2 дараах тоглоомыг тоглож байв. Анх зөвхөн хүрээ нь будагдсан $n × m$ шатрын хөлөг өгөгдсөн. Аннагаас эхлэн ээлж ээлжээр үйлдэл хийнэ. Үйлдэл бүрт өмнө будагдсан тэгш өнцөгтийн дотор арай жижиг тэгш өнцөгтийг будна. Шинэ тэгш өнцөгт нь хуучин тэгш өнцөгттэй ямар ч адил талгүй байна. Жич бид будах тоолондоо хүрээг нь будаж байгаа болно.

Хэн ч тоглоомонд ялахгүй. Бид зүгээр л Анна Мариа 2-ыг $k$ нүүдэл хийтэл тоглоно. Энэ тоглоомыг тоглох хэдэн янзын боломж байгааг тоол.

Оролт

Эхний ганц мөрөнд $n, m, k$ ($1 ≤ n, m, k ≤ 1000$) тоонууд зайгаар тусгаарлагдан өгөгдөнө.

Гаралт

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

Орчуулсан: Энхсанаа

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

Оролт
.......A
........
........
........
........
........
........
M.......
Гаралт
WIN
Оролт
.......A
........
........
........
........
........
SS......
M.......
Гаралт
LOSE
Оролт
.......A
........
........
........
........
.S......
S.......
MS......
Гаралт
LOSE
Сэтгэгдлүүдийг ачааллаж байна...