题目描述

一方通行成功接入了 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$。

输出格式

一行一个整数，表示答案。

样例 1

input

4 2

output

8

样例 2

input

666 233

output

2539518298

数据范围与提示

对于所有数据 $1 \leq N,k \leq 2 \times 10^9$。