Se citesc doua numere naturale n si k. Un gard are n stalpi, fiecare putand fi vopsit cu una dintre cele k culori disponibile. Determinati, folosind Programarea Dinamica, in cate moduri se poate vopsi gardul astfel incat sa nu existe 3 stalpi CONSECUTIVI vopsiti cu aceeasi culoare.
- Date de intrare
- Se citesc, separate prin spatiu, numerele naturale n si k.
- Date de iesire
- Se afiseaza un singur numar: numarul de colorari valide.
- Restrictii
- 1 <= n <= 25, 2 <= k <= 6
Exemple
Exemplul 1
Intrare
3 2
Iesire
6
Exemplul 2
Intrare
1 5
Iesire
5