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.
## Input
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.
## Output
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).
[samples]
## Note
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.
我们称一个大小为 $n$ 的数组 $a$ 为 _互质_ 的，当且仅当 $\gcd(a_1, a_2, ..., a_n) = 1$，其中 $\gcd$ 表示参数的最大公约数。
给定两个数 $n$ 和 $k$。对于每个 $i$（$1 ≤ i ≤ k$），你需要确定满足以下条件的 _互质_ 数组 $a$ 的数量：数组大小为 $n$，且对每个 $j$（$1 ≤ j ≤ n$）都有 $1 ≤ a_j ≤ i$。由于答案可能非常大，你需要对 $10^9 + 7$ 取模计算。
第一行包含两个整数 $n$ 和 $k$（$1 ≤ n, k ≤ 2·10^6$），分别表示目标数组的大小和元素的最大上界。
由于输出 $2·10^6$ 个数字可能耗时很长，你必须以如下方式输出答案：
设 $b_i$ 为元素范围在 $[1, i]$ 内的 _互质_ 数组的数量，对 $10^9 + 7$ 取模。你需要输出 $b_1 \oplus b_2 \oplus \dots \oplus b_k$，对 $10^9 + 7$ 取模。这里 $\oplus$ 表示按位异或运算（C++ 或 Java 中为 _^_，Pascal 中为 _xor_）。
## Input
第一行包含两个整数 $n$ 和 $k$（$1 ≤ n, k ≤ 2·10^6$），分别表示目标数组的大小和元素的最大上界。
## Output
由于输出 $2·10^6$ 个数字可能耗时很长，你必须以如下方式输出答案：设 $b_i$ 为元素范围在 $[1, i]$ 内的 _互质_ 数组的数量，对 $10^9 + 7$ 取模。你需要输出 $b_1 \oplus b_2 \oplus \dots \oplus b_k$，对 $10^9 + 7$ 取模。这里 $\oplus$ 表示按位异或运算（C++ 或 Java 中为 _^_，Pascal 中为 _xor_）。
[samples]
## Note
示例解释：
由于 _互质_ 数组的数量很大，我们将列出非互质但元素仅在范围 $[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$。
Let $ n, k \in \mathbb{N} $, with $ 1 \leq n, k \leq 2 \cdot 10^6 $.
For each $ i \in [1, k] $, define:
- $ A_i = \{ \mathbf{a} \in [1, i]^n \mid \gcd(a_1, a_2, \dots, a_n) = 1 \} $
- $ b_i = |A_i| \mod (10^9 + 7) $
Compute:
$$
\bigoplus_{i=1}^{k} b_i
$$
where $ \oplus $ denotes the bitwise XOR operation.