题目描述

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

子任务编号	分值	$N$	$k$
1	$5$	$\leq 1000$	$\leq2 \times 10^9$
2	$12$	$\leq 10^5$
3	$18$	$\leq 10^7$
4	$15$	$\leq 2 \times 10^9$	$=1$
5	$50$		$\leq 2 \times 10^9$