Rezolvare PBinfo #4569

În parcul orașului există k rânduri de câte n copaci perfect aliniați. Rândurile sunt notate A, B, C … K, iar copacii de pe fiecare rând sunt numerotați de la 1 la n, ca în imaginea de mai jos:

O veveriță jucăușă sare prin copaci astfel:

• pornește dintr-un copac numerotat cu 1;
• la fiecare pas sare dintr-un copac numerotat cu i într-un copac numerotat cu i+1. Dacă se află într-un copac de pe rândul A, va sări în copacul de pe rândul B, iar dacă se află într-un copac de pe rândul K, va sări în copacul de pe rândul K-1. Dacă se află în copacul de pe unul dintre rândurile B, C, D, …K-1 va sări în copacul de pe rândul anterior sau în copacul de pe rândul următor. De exemplu, dacă se află în copacul de pe rândul D, va sări în copacul de pe rândul C sau în copacul de pe rândul E;
• se oprește într-unul dintre copacii numerotați cu n.

Cerința

Aflați numărul M de modalități în care se poate deplasa veverița, respectând regulile de mai sus.

Date de intrare

Fișierul de intrare veverita_xi.in conține pe prima linie numerele n și k.

Date de ieșire

Fișierul de ieșire veverita_xi.out va conține pe prima linie valoarea cerută.

Restricții și precizări

• 1 ≤ n ≤ 50
• 1 ≤ k ≤ 26

Exemplu1

veverita_xi.in

3 3 

veverita_xi.out

6

Explicație

Exemplu2

veverita_xi.in

3 4 

veverita_xi.out

10