H. Dividing
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The following rules define a kind of integer tuple - the Legend Tuple:

  • $$$(1, k)$$$ is always a Legend Tuple, where $$$k$$$ is an integer.
  • if $$$(n, k)$$$ is a Legend Tuple, $$$(n + k, k)$$$ is also a Legend Tuple.
  • if $$$(n, k)$$$ is a Legend Tuple, $$$(nk, k)$$$ is also a Legend Tuple.

We want to know the number of the Legend Tuples $$$(n, k)$$$ where $$$1 \le n \le N, 1 \le k \le K$$$.

In order to avoid calculations of huge integers, report the answer modulo $$$10^9+7$$$ instead.

Input

The input contains two integers $$$N$$$ and $$$K$$$, $$$1 \le N, K \le 10^{12}$$$.

Output

Output the answer modulo $$$10^9+7$$$.

Examples
Input
3 3
Output
8
Input
3 9
Output
14