CF915G.Coprime Arrays

Let's call an array a of size n coprime iff gcd(_a_1, _a_2, ..., a__n) = 1, where gcd is the greatest common divisor of the arguments.

You are given two numbers n and k. For each i (1 ≤ i ≤ k) you have to determine the number of coprime arrays a of size n such that for every j (1 ≤ j ≤ n) 1 ≤ a__j ≤ i. Since the answers can be very large, you have to calculate them modulo 109 + 7.

我们称一个长度为 $ n $ 的数组 $ a $ 是互质的，当且仅当 $ \gcd(a_1,,a_2,,\dots,,a_n) = 1 $，其中 $ \gcd $ 表示其参数的最大公约数。

给定两个整数 $ n $ 和 $ k $。对每个 $ i $（$ 1 \le i \le k $），你需要计算满足以下条件的互质数组 $ a $（长度为 $ n $）的个数：对每个 $ j $（$ 1 \le j \le n $），均有 $ 1 \le a_j \le i $。由于答案可能非常大，你需将结果对 $ 10^9 + 7 $ 取模。

The first line contains two integers n and k (1 ≤ n, k ≤ 2·106) — the size of the desired arrays and the maximum upper bound on elements, respectively.

第一行包含两个整数 $n$ 和 $k$（$1 \leq n, k \leq 2 \cdot 10^6$），分别表示所求数组的大小以及元素的最大上界。

Since printing 2·106 numbers may take a lot of time, you have to output the answer in such a way:

Let b__i be the number of coprime arrays with elements in range [1, i], taken modulo 109 + 7. You have to print , taken modulo 109 + 7. Here denotes bitwise xor operation (^ in C++ or Java, xor in Pascal).

由于输出 $2 \times 10^6$ 个数可能耗时较长，你需要按如下方式输出答案：

设 $b_i$ 表示元素取值范围为 $[1,\,i]$ 的互质数组的个数（对 $10^9 + 7$ 取模）。你需要输出

（对 $10^9 + 7$ 取模）。其中

表示按位异或运算（C++ 或 Java 中为 ^，Pascal 中为 xor）。

Explanation of the example:

Since the number of coprime arrays is large, we will list the arrays that are non-coprime, but contain only elements in range [1, i]:

For i = 1, the only array is coprime. _b_1 = 1.

For i = 2, array [2, 2, 2] is not coprime. _b_2 = 7.

For i = 3, arrays [2, 2, 2] and [3, 3, 3] are not coprime. _b_3 = 25.

For i = 4, arrays [2, 2, 2], [3, 3, 3], [2, 2, 4], [2, 4, 2], [2, 4, 4], [4, 2, 2], [4, 2, 4], [4, 4, 2] and [4, 4, 4] are not coprime. _b_4 = 55.

示例解释：

由于互质数组的数量很大，我们将列出那些非互质但所有元素均在范围 $[1,\,i]$ 内的数组：

当 $i = 1$ 时，唯一数组是互质的，故 $b_1 = 1$。

当 $i = 2$ 时，数组 $[2,\,2,\,2]$ 不是互质的，故 $b_2 = 7$。

当 $i = 3$ 时，数组 $[2,\,2,\,2]$ 和 $[3,\,3,\,3]$ 均不是互质的，故 $b_3 = 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]$，
故 $b_4 = 55$。