Cerința

Johnnie Walker este acum in București! Chiar dacă este târziu, el vrea totuși să facă o plimbare. Cartierul în care locuiește Johnnie poate fi reprezentat ca un graf neorientat complet cu n noduri, unde străzile sunt reprezentate ca muchii și intersecțiile ca noduri.

În orice moment de timp, Johnnie poate să meargă către orice intersecție adiacentă cu cea în care se afla și îi va lua exact un minut să se deplaseze. Pentru că lui Johnnie nu-i place să aștepte, el se va deplasa către o altă intersecție în fiecare minut.

Johnnie e acum curios câte drumuri există astfel încât drumul lui va dura exact k minute și va ajunge înapoi în intersecția de unde și-a început drumul. La început, Johnnie se află în prima intersecție(nodul 1).

Două drumuri sunt diferite dacă există o poziție unde cele două intersecții diferă. Johnnie poate să treaca printr-o intersecție de mai multe ori pe parcursul drumului său.

Ajutați-l să afle răspunsul la întrebarea sa. Fiindcă valoarea poate fi destul de mare, el vă cere doar să afișați restul valorii la 666013.

Date de intrare

Programul citește de la tastatură două numere, n și k, cu descrierea din enunț.

Date de ieșire

Programul va afișa pe ecran răspunsul la întrebarea lui Johnnie, modulo 666013.

Restricții și precizări

• 1 ≤ n ≤ 109
• 1 ≤ k ≤ 1018
• Pentru teste în valoare de 10 puncte, 1 ≤ n ≤ 5 și 1 ≤ k ≤ 10.
• Pentru alte teste în valoare de 20 de puncte, 1 ≤ n * k ≤ 2 000 000.
• Pentru alte teste în valoare de 20 de puncte, 1 ≤ k ≤ 1 000 000.

Exemplu:

Intrare

4 3

Ieșire

6

Exemplu:

Intrare

5 3

Ieșire

12

Exemplu:

Intrare

100 15799

Ieșire

543264

Explicație

Pentru primul exemplu, cele 6 drumuri valide sunt:

1 -> 2 -> 3 -> 1

1 -> 2 -> 4 -> 1

1 -> 3 -> 2 -> 1

1 -> 3 -> 4 -> 1

1 -> 4 -> 2 -> 1

1 -> 4 -> 3 -> 1