Se citeste un sir de cifre. Folosind maparea A=1, B=2, ..., Z=26, un astfel de sir poate reprezenta o codificare a unui mesaj format din litere mari. Determinati, folosind Programarea Dinamica, in cate moduri distincte poate fi decodat sirul (grupand cifrele in numere de 1 sau 2 cifre, fiecare intre 1 si 26, fara zerouri nesemnificative).
- Date de intrare
- Se citeste sirul de cifre.
- Date de iesire
- Se afiseaza un singur numar: numarul de decodari posibile (0 daca sirul nu poate fi decodat in niciun mod valid).
- Restrictii
- 1 <= lungimea sirului <= 1000
Exemple
Exemplul 1
Intrare
12
Iesire
2
Exemplul 2
Intrare
226
Iesire
3