问题描述

众所周知, 当 \(x\) 的质因数分解为 \(\displaystyle \prod_i p_i^{a_i}\) 时, 有:

\[\mu(x) = \displaystyle \prod_i (-1)^{a_i} [a_i \leq 1]\]

类似地, 定义:

\[f_k(x) = \displaystyle \prod_i (-1)^{a_i} [a_i \leq k]\]

现在给定 \(n, k\), 求

\[\sum_{i=1}^{n} \sum_{j=1}^{n} \sum_{d=1}^{k} f_d(\gcd(i, j)) \pmod{2^{30}}\]

输入格式

仅两个整数, 分别表示 \(n, k\).

输出格式

仅输出一个整数, 表示 \(\displaystyle \sum_{i=1}^{n} \sum_{j=1}^{n} \sum_{d=1}^{k} f_d(\gcd(i, j))\) 对 \(2^{30}\) 取模后的值.

数据范围

对于 \(100\%\) 的数据, \(0 < n \leq 10^{10}\), \(0 < k \leq 40\).