Masala #ZH96B5ZO0D

Xotira 512 MB Vaqt 1000 ms

Raqamli o'yin

Sizga \(N×M\) o‘lchamli matritsa beriladi. Matritsaning har bir elementi \(0\) dan \(9\) gacha bo‘lgan bitta raqamdan iborat. Siz matritsaning yuqori chap burchagini \((0,0)\) nuqtasi, pastki o‘ng burchagini esa \((N−1,M−1)\) nuqtasi deb olasiz. Har bir qadamda faqat yuqoridagi, pastdagi, chapdagi yoki o‘ngdagi raqamni qo'shish mumkin. Har bir elementni yo‘l davomida faqat bir marta qo'shish mumkin (takroriy qo'shish ruxsat etilmaydi). Berilgan matritsa uchun boshlang‘ich nuqta \((0,0)\) dan oxirgi nuqta \((N−1,M−1)\) gacha borgan, va hosil bo‘lgan yig'indi \(K\) ga bo‘linadigan barcha yo‘llar sonini aniqlang. Yig'indi hisoblanayotganda \((0,0)\)va \((N-1,M-1)\) indexlarda joylashgan raqamlarni yig'indiga olinmaydi.

Kiruvchi ma'lumotlar:

Birinchi qatorda \(N,M,K\) butun sonlari \(N,M(2≤N,M≤6). K(1≤K≤100).\)

Chiquvchi ma'lumotlar:

Yagona qatorda masala yechimini chop eting.

Misollar

#	input.txt	output.txt
1	2 2 3 1 3 3 4	2
2	3 3 2 1 2 3 4 5 6 7 8 9	12
3	3 3 2 1 1 1 1 2 1 1 1 1	10

Izoh:

1-testni ko'rib chiqsak.

2x2 matritsa berilgan. K = 3 bo'lsa

[1 3]

[3 4]

Jami 2 ta yo'l bor. Ikkisining ham yig'indisi 3 ga teng va bu 3 ga qoldiqsiz bo'linadi.