Î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:
![](http://info.mcip.ro/veveritak.png)
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 cui+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. Datorită faptului că numărul M
este foare mare, se afișa restul împărțirii lui M
la 666013
.
Date de intrare
Fișierul de intrare veveritak.in
conține pe prima linie numerele n
și k
.
Date de ieșire
Fișierul de ieșire veveritak.out
va conține pe prima linie valoarea cerută.
Restricții și precizări
1 ≤ k ≤ 26
1 ≤ n ≤ 10
9
- pentru 40% din teste,
n ≤ 1000000
;
Exemplu
veveritak.in
3 3
veveritak.out
6