D. Петя болон Будалт

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

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

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

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

Бяцхан Петя тоолох дуртай. Тэр $k$ ширхэг будагаар $n × m$ ($n$ мөр, $m$ багана) хэмжээтэй самбарыг хэдэн янзаар будаж болохыг тоолохыг хүсэж байгаа. Тэр будахдаа дурын босоо баганы дагуу самбарыг $2$ хоосон биш хэсэгт хуваахад $2$ талд байх ялгаатай өнгөний тоо тэнцүү байхаар будах ёстой. Петяд самбарыг хэдэн янзаар будаж болохыг тоолоход нь тусална уу.

Оролт

Эхний мөрөнд хөлгийн хэмжээ болох $n, m$ тоонууд болон $k$ тоо өгөгдөнө. ($1 ≤ n, m ≤ 1000$, $1 ≤ k ≤ 10^6$)

Гаралт

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

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

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

Оролт
2 2 1
Гаралт
1
Оролт
2 2 2
Гаралт
8
Оролт
3 2 2
Гаралт
40
Сэтгэгдлүүдийг ачааллаж байна...