E. LCM Plus GCD
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two integers, $$$x$$$ and $$$k$$$. Your task is to determine the total number of sets that contain exactly $$$k$$$ distinct positive integers $$$a_1, a_2, ..., a_k$$$ such that the sum of their Least Common Multiple (LCM) and Greatest Common Divisor (GCD) equals $$$x$$$, i.e. $$$\operatorname{LCM}(a_1,a_2,\ldots, a_k)+\operatorname{GCD}(a_1,a_2,\ldots, a_k)=x$$$.

The LCM of a set of numbers is the smallest positive integer that each number in the set can divide, while the GCD is the largest positive integer that can divide each number in the set. For instance, $$$\operatorname{LCM}(4,6,8)=24$$$ and $$$\operatorname{GCD}(4,6,8)=2$$$.

As the result could potentially be a very large number, you should provide the output modulo $$$10^9 + 7$$$.

Input

One line contains two integers $$$x$$$ and $$$k$$$ ($$$1\le x, k \le 10^9$$$).

Output

Output an integer denoting the answer modulo $$$10^9 + 7$$$.

Examples
Input
14 2
Output
3
Input
14 3
Output
4