Masala #0621

Xotira 256 MB Vaqt 1000 ms
14

Rangli panjara #2

\(K\) ranglardan foydalanib \(N * M\) panjarani rang berish usullari sonini hisoblang. Panjaradagi qo'shni kvadratlar turli xil ranglarga ega bo'lishi kerak. Agar ular bir chekkaga ega bo'lsa o'sha kataklar bir xil ranga bo'yaladi. (Izohda misol berilgan)


Kiruvchi ma'lumotlar:

Birinchi qatorda \(T (1 \le T \le 15)\) testlar soni kiritiladi.

Keyingi \(T\) ta qatorda \(N,M (1 \le N , M \le 8)\) va \(K (1 \le K \le 10^7)\) sonlari kiritiladi.


Chiquvchi ma'lumotlar:

Har bir test uchun panjaraga rang berish usullarini \(10^9+7\) ga bo'lgandagi qoldiqni toping.


Misollar
# input.txt output.txt
1
1
3 3 2
2
2
8
1 5 6
6 5 2
3 5 6
1 2 5
3 6 5
2 6 1023
8 8 1236
4 5 12365468
2
78062727
20
774950910
583468902
165901354
936552080
150154877
Izoh:

1-test uchun:

1-test uchun 2 ta holat mavjud: