Î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. 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 ≤ 109
• pentru 40% din teste, n ≤ 1000000;

Exemplu

veveritak.in

3 3 

veveritak.out

6

Explicație