Totient LCM Product

Given two positive integers n and k, compute the following product modulo \(10^9+7\):

\[ \prod_{i_1=1}^{n}\prod_{i_2=1}^{n}\cdots\prod_{i_k=1}^{n} \varphi\big(\mathrm{lcm}(i_1,i_2,\ldots,i_k)\big)\]

Here, \(\mathrm{lcm}(i_1,i_2,\ldots,i_k)\) denotes the least common multiple of the \(k\) numbers (note that for a single number, its lcm is defined to be itself), and \(\varphi(\cdot)\) represents Euler's totient function. The product symbol \(\prod\) denotes repeated multiplication.

You are required to output the computed product modulo \(10^9+7\).

inputFormat

The input consists of a single line containing two space-separated integers n and k.

Constraints: It is guaranteed that the input values are small enough for a brute force solution to pass all test cases.

outputFormat

Output a single integer --- the value of the product modulo \(10^9+7\).

sample

2 1

1