Codeforces Round #804 (Div. 2)
5 өдрийн дараа |
B. Ялгаатай замууд
хугацааны хязгаарлалт 2 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Танд $n × m$ нүдтэй тавцан байгаа ба зарим нүд нь аль хэдий нь будагдчихсан, зарим нь будагдаагүй. Нийт $к$ ширхэг ялгаатай будаг бий. Таны даалгавар бол зүүн дээд нүднээс баруун доод нүд хүртэлх замуудаас ядаж нэг нь хоёр ижил өнгөтэй нүд агуулаагүй байхаар тооцож будагдаагүй байгаа нүднүүдийг будах юм.
Дээрх шаардлагыг хангасан байх ялгаатай будалтуудын тоог $1000000007 (10^9 + 7)$-д хуваасан үлдэгдлийг хэвлэ.
Оролт
Эхний мөрөнд $n, m, k (1 ≤ n, m ≤ 1000, 1 ≤ k ≤ 10)$ гурван бүхэл тоо орж ирнэ. Дараагийн n ширхэг мөр нь m ширхэг тоонуудыг агуулах ба эдгээр нь тавцангийн нүднүүдийг илэрхийлэх болно. Тухайн нүд будагдаагүй бол 0 гэсэн утгатай, будагдсан бол будгийн дугаартай(1-ээс k) байна.
Гаралт
Боломжит будалтуудын тоог $1000000007 (10^9 + 7)$-д хуваасан үлдэгдлийг хэвлэ.
[Орчуулга хяналт хийгдээгүй. ^_^ ... Codeforces Mongolian Translation Team]
Орчуулсан: mmur
Жишээ тэстүүд
Оролт
2 2 4 0 0 0 0
Гаралт
48
Оролт
2 2 4 1 2 2 1
Гаралт
0
Оролт
5 6 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Гаралт
3628800
Оролт
2 6 10 1 2 3 4 5 6 0 0 0 0 0 0
Гаралт
4096