Coprime Arrays
题意翻译
#### 题意：
我们称一个大小为 $n$ 的数组 $a$ 互质，当且仅当 $gcd(a_1,a_2,\cdots,a_n)=1$，$gcd$ 是最大公约数的意思。
给定 $n,k$，对于每个 $i$ $(1\le i\le k)$，你都需要确定这样的数组的个数——长度为 $n$ 的互质数组 $a$ ，满足对每个 $j$ $(1\le j\le n)$，都有 $1\le a_j\le i$。
答案可能非常大，请对 $10^9+7$ 取模。
#### 输入格式：
只有一行，两个数 $n,k$ $(1\le n,k\le 2\cdot10^6)$，分别表示数组的大小和数组元素大小的上限。
#### 输出格式：
为了降低输出的时间，你需要对输出进行如下处理：
把 $i$ 的答案（对 $10^9+7$ 取模后）记作 $b_i$。你需要输出 $\sum_{i=1}^{k} (b_i\oplus i)$，再对 $10^9+7$ 取模。
这里 $\oplus$ 表示按位异或，在 c++ 和 Java 中写作 ```^```，在 Pascal 中写作 ```xor```。
#### 说明：
第一个样例的说明：
因为互质数组的数量比较多，我们只列出不互质的：
当 $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$。
Translated by 小粉兔
题目描述
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 $ 10^{9}+7 $ .
输入输出格式
输入格式
The first line contains two integers $ n $ and $ k $ ( $ 1<=n,k<=2·10^{6} $ ) — the size of the desired arrays and the maximum upper bound on elements, respectively.
输出格式
Since printing $ 2·10^{6} $ 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 $ 10^{9}+7 $ . You have to print , taken modulo $ 10^{9}+7 $ . Here  denotes bitwise xor operation (^ in C++ or Java, xor in Pascal).
输入输出样例
输入样例 #1
3 4
输出样例 #1
82
输入样例 #2
2000000 8
输出样例 #2
339310063
说明
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 $ .