Fall FLASG | Biblioteca

"Nici un om nu ar asterne vreun cuvant pe hartie daca ar avea curajul sa traiasca intr-adevar lucrurile in care crede." - Henry Miller

ASG vizitează Biblioteca orașului și observă că fiecare raft are o lungime de $N$ și o înălțime de 4. Fiecare carte are o lungime de 2 și o lățime de 1. ASG dorește să afle câte moduri diferite există pentru a aranja cărțile pe cele $K$ rafturi astfel încât fiecare raft să fie umplut complet (fără spații libere), iar configurațiile rafturilor să fie unică, indiferent dacă le privești de la stânga la dreapta sau viceversa.

Date de intrare

Pe prima linie se găsește două numere, $N$ și $K$, cu semnificația din enunț.

Date de ieșire

Se va afișa în câte modalități putem pune cărțile pe cele $K$ rafturi, astfel încât dacă luăm oricare $2$ modalități de a plasa cărțile, există cel puțin un raft care diferă. Pentru că valoarea este foarte mare, să se afișeze restul împărțirii la $666 \ 013$

Restricții și precizări

• $1 \leq N \leq 10^{18}$
• $1 \leq K < 666 \ 013$

Exemplul 1

stdin

2 3

stdout

10

Explicație

Numărul de moduri de a plasa pe un raft de dimensiune $2 \cdot 4$ cărție de dimensiune $1 \cdot 2$:

Exemplul 2

stdin

3 1

stdout

11

Exemplul 3

stdin

88 132

stdout

505231