让我们将大小为 n 的数组 a 称为互质 iff gcd(a1, a2, ..., an) = 1,其中 gcd 是参数的最大公约数。
给你两个数字 n 和 k。对于每个 i (1 ≤ i ≤ k),您必须确定大小为 n 的互质数组 a 的数量,使得对于每个 j (1 ≤ j ≤ n) 1 ≤ aj ≤ i。由于答案可能非常大,因此您必须以 109 + 7 为模来计算它们。
输入
第一行包含两个整数 n 和 k (1 ≤ n, k ≤ 2·106) — 分别是所需数组的大小和元素的最大上限。
输出
由于打印 2·106 个数字可能需要很长时间,因此必须以这样的方式输出答案:
设 bi 为元素在 [1, i] 范围内的互质数组的数量,以 109 + 7 为模。您必须打印 $$\sum_{i=1}^{k}(b_i \oplus i)$$,以 109 + 7 为模。这里 $$\bigcirc$$ 表示按位异或运算(^ 在 C++ 或 Java 中,xor 在帕斯卡)。
示例
输入 #1
3 4
输出 #1
82
输入 #2
2000000 8
输出 #2
339310063
注意
示例说明:
由于互质数组的数量很大,我们将列出非互质的数组,但仅包含范围 [1, i] 中的元素:
对于 i = 1,唯一的数组是互质的。 b1 = 1。
对于 i = 2,数组 [2, 2, 2] 不是互质的。 b2 = 7。
对于 i = 3,数组 [2, 2, 2] 和 [3, 3, 3] 不是互质的。 b3 = 25。
对于 i = 4,数组 [2, 2, 2]、[3, 3, 3]、[2, 2, 4]、[2, 4, 2]、[2, 4, 4]、[4, 2, 2]、[4, 2, 4]、[4, 4, 2] 和 [4, 4, 4] 不是互质的。 b4 = 55。