Gigel este preocupat de probleme cu şiruri de numere naturale. Azi el s-a gândit să analizeze doar şirurile distincte cu acelaşi număr K de termeni. Gigel vrea sa afle numărul de şiruri distincte de K termeni cu proprietatea că pentru fiecare şir cel mai mic multiplu comun al termenilor este egal cu N.
Cerinţă
El a constatat că acest număr de şiruri distincte este mare şi de aceea, ar dori să afle doar restul împărţirii acestui număr la 104.
Date de intrare
Datele se citesc din fişierul ultime4.in, ce are pe prima linie numerele N şi K separate printr-un singur spaţiu.
Date de ieşire
Numărul cerut se va scrie pe prima linie în fişierul ultime4.out.
Restricţii
1 <= N, K < 109
Exemplu
ultime4.in
ultime4.out
Explicaţie
3 2
3
Cele 3 şiruri distincte de câte 2 elemente care au cel mai mic multiplu comun al termenilor egal cu 3 sunt: (1,3), (3,1) şi (3,3)