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

Cerința

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 multiplu1.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 multiplu1.out va conține pe prima linie un singur număr natural reprezentând rezultatul cerut.

Restricții și precizări

• 0 < N ≤ 1 000 000 000
• 0 < K ≤ 1 000 000 000

Exemplu:

multiplu1.in

5 2

multiplu1.out

3

Explicație

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