Rock lives in a $k$-dimensional world. In his warehouse, there are $N$ boxes in it.
He likes to arrange his boxes in a $k$-dimensional hypercube. In particular, he would arrange his boxes in the following manner:

• $l_1$ boxes in the first dimension of the warehouse (i.e. the length)
• $l_2$ boxes in the second dimension of the warehouse (i.e. the width)
• ⋮
• So that $l_1 \times l_2 \times \dots \times l_k = N$

Now, he wonders how many ways he can have this arrangement. Two arrangements are considered different if one of their dimensions differ. For example, $12 = 2 \times 2 \times 3 = 2 \times 3 \times 2$ are two different ways. As the answer can be quite large, output it modulo $10^9 + 7$.

Input

The first line consists of two integers $N$ and $k$.

Output

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

Constraints

For all testcases: $1 \le k \le 10^6, 1 \le N \le 10^9$
Subtask 1 (10%): $k=2$
Subtask 2 (90%): No other constraints