multiplu

Se consideră două numere naturale nenule $N$ şi $K$. Numim $K$-şir un şir de numere naturale cu $K$ termeni.

Cerinţă

Determinaţi numărul format din ultimele $4$ cifre ale numărului de $K$-şiruri distincte cu proprietatea că fiecare dintre ele are cel mai mic multiplu comun al termenilor egal cu $N$.

Date de intrare

Fişierul de intrare multiplu.in conţine pe prima linie cele două numere $N$ şi $K$ separate printr-un singur spaţiu.

Date de ieșire

Fişierul de ieşire multiplu.out conţine un singur număr natural reprezentând rezultatul cerut.

Restricții și precizări

• $1 \leq N, K \leq 10^9$;

Exemplu

multiplu.in

5 2

multiplu.out

3

Explicație

Cele $3 \ 2$ - şiruri cu cel mai mic multiplu comun al termenilor egal cu $5$ sunt: ($1, 5$), ($5, 1$) şi ($5, 5$)