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
Орчуулгыг засах?
Сэтгэгдлүүдийг ачааллаж байна...