Prihlásenie Registrácia  

C - Jozef

Č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 ]

Jozef sa má o chvíľu stretnúť so svojou priateľkou Barborou. Keďže sa blížia jej meniny, 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 ešte 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á Jozef na nazbieranie kvetov do kytice. Lúku môžeme reprezentovať ako obdĺžnik, Jozef na začiatku sa nachádza v jeho ľavom hornom rohu. Pohyb Jozefa 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 Jozefa. 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 1 ≤ K ≤ 100.
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.

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
^76
595
68$

Výstup:

10
2