Problem Description

In particular, the LCM of a single number is the number itself.

Kind dkw decides to tell you the statement directly:

$$\prod_{i_1=1}^n\prod_{i_2=1}^n …\prod_{i_k=1}^n \varphi\big(lcm(i_1,i_2,…,i_k)\big)$$

Please compute the expression above, and output the answer modulo $10^9+7$.

Here, $lcm(i_1,i_2,...,i_k)$ denotes the least common multiple of these $k$ numbers.

Here, $\varphi$ denotes Euler's totient function.

Here, $\prod$ denotes the product symbol, which is the multiplicative version of $\sum$.

Input Format

Two positive integers, $n,k$.

Output Format

One non-negative integer, representing the value of the expression modulo $10^9+7$.

2 2

1

Hint

For 50% of the testdata, $1\le n,k\le 8$.

For 100% of the testdata, $1\le n,k\le 10^6$.

Translated by ChatGPT 5