一方通行成功接入了 Misaka Network。
现在他要使用超能力，自然计算式被送到了御坂网络进行处理。这次的计算式是这样子的：
\sum_{i=1}^{N}\sum_{j=1}^{N}f(\gcd(i,j))^k \bmod 2^{32}
其中 f(x) 表示 x 次大的质因数，重复的质因数计算多次，例如 f(6)=2,f(4)=2 。规定 f(1)=0,f(p)=1 ，其中 p 为质数。
但是妹妹们都不会算这个式子……所以御坂 20001 号找到了你，希望你帮她算一下。
一行两个正整数 N 和 k 。
一行一个整数，表示答案。
4 2
8
666 233
2539518298
对于所有数据 1 \leq N,k \leq 2 \times 10^9 。
