Un mare împărat chinez a ajuns la un număr impresionant de victorii, notat cu m. Pentru a cinsti cum se cuvine acest eveniment ordonă consilierului său fabricarea unui covor lung de k metri şi lat de 2 metri pe care să-l pună de la intrarea în cetate până la intrarea în castel. Pentru că împăratul este un împătimit al calculelor matematice doreşte ca acest covor să fie alcătuit din pătrăţele de latură 1 metru, având diferite culori. Pentru k=10 covorul are forma:

Culorile sunt codificate cu diverse numere naturale şi trebuie să fie alese astfel încât să cinstească victoriile împăratului, adică numerele folosite la codificarea culorilor pătratelor de pe aceeaşi coloană trebuie să aibă cel mai mic multiplu comun egal cu m şi nu trebuie să existe două coloane colorate la fel.
Dacă notăm cu a₁, a₂, ..., a_k codurile culorilor de pe linia de sus, respectiv cu b₁, b₂, ..., b_k codurile culorilor de pe linia de jos a covorului, atunci condiţiile de mai sus se pot scrie astfel:

• pentru i=1,2,...,k, cel mai mic multiplu comun pentru a_i şi b_i este m;
• pentru i<j, i,j=1,2,…,k, (a_i,b_i)≠(a_j,b_j)   

Covorul pus de la intrarea în cetate până la castel trebuie să fie mereu curat şi de aceea se doreşte fabricarea unui număr cât mai mare de covoare diferite care să respecte condiţiile împăratului.
Două covoare sunt considerate diferite dacă există o poziţie (i, j) (1≤i≤2 şi 1≤j≤k) astfel încât culoarea pătratului de pe linia i şi coloana j în primul covor este diferită de culoarea pătratului de pe linia i şi culoarea j în al doilea covor.

Cerinţă

Să se scrie un program care, cunoscând m şi k, determină numărul maxim de covoare diferite care pot fi fabricate în condiţiile din enunţ.

Date de intrare

Fişierul de intrare covor.in conţine pe prima linie numerele naturale m şi k separate printr-un spaţiu.

Date de ieşire

Fişierul de ieşire covor.out va conţine o singură linie  pe care va fi scris numărul maxim de covoare diferite ce se pot fabrica, modulo 9901.

Restricţii

• 1 ≤ m,k ≤ 2000000000
• Pentru codificarea culorilor se poate folosi orice număr natural.
• p modulo h reprezintă restul împărţirii lui p la h.

Exemple

covor.in	covor.out	Explicaţie
6 4	3024	Iată 4 covoare dintre cele posibile: În fiecare pătrăţel este scris codul unei culori.

prof. Doru Popescu Anastasiu

C.N. "Radu Greceanu", Slatina

dopopan@yahoo.com