Matei are o tastatura numerica cu 17 taste: Num, /, *, -, 7, 8, 9, +, 4, 5, 6, 1, 2, 3, Enter, 0, Del, asezate ca pe un tastatura numerica obisnuita (tasta 0 este lata si atinge tastele 1 si 2, iar tastele + si Enter sunt inalte si ating cate 4, respectiv 3 taste vecine). Doua taste sunt alaturate daca sunt diferite si se ating pe o latura sau jumatate de latura (vecinatatea pe diagonala nu conteaza). Matei apasa in total pe K taste. Prima tasta poate fi oricare dintre cele 17, iar incepand cu a doua apasare, fiecare tasta apasata trebuie sa fie alaturata celei apasate anterior. In cate moduri poate Matei apasa pe cele K taste?
- Date de intrare
- Se citeste de la tastatura un singur numar natural K, numarul total de apasari.
- Date de iesire
- Se afiseaza pe ecran numarul de moduri in care Matei poate apasa K taste.
- Restrictii
- 1 <= K <= 30
Exemple
Exemplul 1
Intrare
1
Iesire
17
Exemplul 2
Intrare
2
Iesire
56