M1 - MDŽ

Časový limit: 2s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3

Počet bodov: 1

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Tomáš sa má o chvíľu stretnúť s priateľkou. Keďže je dnes Medzinárodný deň žien, tak ju chce prekvapiť vlastnoručne natrhanou kyticou lúčnych kvetov. Nemá už veľa času, ale po ceste k priateľke má jednu lúku, kde už teraz rastie zopár kvetov. Prichádza k nej z lesa a potrebuje sa dostať na opačný roh lúky. Rozhodol sa, že kyticu vytvorí z 19 kvetov. Keď príde na nejaké miesto s kvetmi, tak odtrhne všetky kvety na ňom. Aby na stretnutie nemeškal, tak sa musí stále približovať ku koncu lúky - nemôže sa teda vrátiť späť.

Vašou úlohou je napísať program, ktorý spočíta koľko možností má Tomáš na nazbieranie kvetov do kytice. Lúku môžeme reprezentovať ako obdĺžnik, Tomáš na začiatku sa nachádza v jeho ľavom hornom rohu. Pohyb Tomáša je teda vpravo, dole a šikmo vpravo dole.

Úloha

Pre zadané rozmiestnenie kvetov na lúke a počet kvetov potrebných na kyticu, vypočítajte počet rôznych ciest Tomáša. Jeho úlohou je nazbierať presný počet kvetov.

Vstup

Prvý riadok obsahuje počet testovacích sád T - kladné celé číslo.
Prvý riadok každej sady obsahuje tri celé kladné čísla, počet riadkov 1 ≤ R ≤ 100, počet stĺpcov 1 ≤ S ≤ 100 a počet želaných kvetov K.
Nasleduje R riadkov s S znakmi reprezentujúcu lúku. Môžete predpokladať, že ľavý horný roh obsahuje znak '^' (označenie začiatku), pravý dolný roh znak '$' (označenie konca). Znak '.' reprezentuje prázdne políčko, '#' políčko obsadené stromom a znaky '1' až '9' predstavujú počet kvetov na jednom políčku/mieste.

M1

Číslo 1 ≤ K ≤ 20 je rovné počtu kvetov na celej lúke. Znaky '1' predstavujú políčko s kvetom. Na jednom políčku sa nachádza najviac jeden kvet.

M2

1 ≤ K ≤ 100
Znaky '1' až '9' predstavujú počet kvetov na jednom políčku.

Výstup

Výstup obsahuje pre každú testovaciu sadu jeden riadok, obsahujúci jedno celé číslo - počet možností modulo 999983.

Príklad

Vstup:

2
4 10 3
^....1#...
.......1..
.........1
.........$
3 3 19
^56
798
65$

Pozn.: Druhá testovacia sada sa týka úlohy M2.

Výstup:

10
2

14 Domáce 2