Least Common Multiple

Time limit2sMemory limit1024 MB

Summary

Given n and k, count the multisets of k positive integers whose least common multiple is exactly n, modulo 10^9+7.

Level: Medium6 of 10
Topics: Number theory, Combinatorics, Math
Solved: No attempts yet

Problem

Vasya is a young programmer. He can already solve problems on graphs, data structures, combinatorics, and dynamic programming. He is not yet familiar with number theory, so he started attending lectures on it. At one of the first lectures he learned what the least common multiple is.

A multiset is a set in which elements may repeat.

The least common multiple of a multiset $S$ of positive integers is the smallest positive integer that is divisible by every element of $S$ .

After each lecture, the teacher assigns homework on the topics covered. This time the assignment was hard:

Given numbers $n$ and $k$, find the number of multisets of $k$ elements whose least common multiple is equal to $n$

For example, if $n = 6$ and $k = 2$ , the suitable multisets are $\{1, 6\}$ , $\{2, 3\}$ , $\{2, 6\}$ , $\{3, 6\}$ , and $\{6, 6\}$ . So the answer is 5. Multisets that differ only in the order of their elements are considered the same.

Vasya understood the lecture very well and is clever, so he has already solved the problem. He is not sure that he did everything correctly. Vasya asks you to solve the same problem and check his answers on some tests. Since the answer may be very large, Vasya only needs the remainder of the answer modulo $10^9+7$ .

Input

The first line of the input contains the numbers $n$ ( $1 \le n \le 10^{12}$ ) and $k$ ( $1 \le k \le 100$ ), separated by a space.

Output

Print one number: the answer modulo $10^9+7$ .

Examples2

Example 1
Input
```
6 2
```
Expected output
```
5
```
Example 2
Input
```
239 3
```
Expected output
```
3
```