Description

这一天,亦遥在学习基础数学时,遇到了一道题,他并不会做,就把这道题抛给了你。

给定$n,k$,表示一共进行$k$次操作，每次会把$n$等概率变成$n$的某个约数。

求操作$k$次后$n$的期望，答案对$10^9+7$取模。

Format

Input

两个正整数$n,k$

Output

输出一个整数

Samples

6 2

875000008

Limitation

对于$10\%$的数据$n=1$;

对于$30\%$的数据$n \leqslant 20,k \leqslant 10$;

对于$50\%$的数据$n \leqslant 1000,k \leqslant 100$;

对于$100\%$的数据$n \leqslant 10^{15},k \leqslant 10^4$