Coprime Arrays
Contest: Educational Codeforces Round 36 (Rated for Div. 2)
Difficulty rating: 2300
Tags: math, number theory

Let's call an array a of size n coprime iff gcd(a1, a2, ..., an) = 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 ≤ aj ≤ i. Since the answers can be very large, you have to calculate them modulo 109 + 7.

Input format:
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 format:
Since printing 2·106 numbers may take a lot of time, you have to output the answer in such a way:

Let bi be the number of coprime arrays with elements in range [1, i], taken modulo 109 + 7. You have to print $$\sum_{i=1}^{k}(b_i \oplus i)$$, taken modulo 109 + 7. Here $$\bigcirc$$ denotes bitwise xor operation (^ in C++ or Java, xor in Pascal).

Constraints:
Time limit: 3.5 s
Memory limit: 256.0 MB

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. b1 = 1.

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

For i = 3, arrays [2, 2, 2] and [3, 3, 3] are not coprime. b3 = 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. b4 = 55.

Example input:
3 4

Example output:
82

Example input:
2000000 8

Example output:
339310063

Editorial:
For a fixed upper bound i, this is a well-known problem that can be solved using inclusion-exclusion:
Let's denote by f(j) the number of arrays with elements in range [1, i] such that gcd(a1, ..., an) is divisible by j. Obviously, $$f(j) = \left(\left\lfloor\frac{i}{j}\right\rfloor\right)^n$$. With the help of inclusion-exclusion formula we can prove that the number of arrays with gcd = 1 is the sum of the following values over all possible sets S: ( - 1)|S|f(p(S)), where S is some set of prime numbers (possibly an empty set), and p(S) is the product of all elements in the set. f(p(S)) in this formula denotes the number of arrays such that their gcd is divisible by every number from set S.
However, the number of such sets S is infinite, so we need to use the fact that f(j) = 0 if j > i. With the help of this fact, we can rewrite the sum over every set S in such a way: $$\sum_{j=1}^{i}\mu(j)f(j)$$, where μ (j) is 0 if there is no any set of prime numbers S such that p(S) = j, |μ (j)| = 1 if this set S exists, and the sign is determined by the size of S (μ (j) = 1 if |S| is even, otherwise μ (j) =  - 1).
An easier way to denote and calculate μ (j) is the following (by the way, it is called Möbius function):
μ(j) = 0, if there is some prime number p such that p2|j. Otherwise μ(j) = ( - 1)x, where x is the number of primes in the factorization of j.
Okay, so we found a solution for one upper bound i, it's $$\sum_{j=1}^{i}\mu(j)f(j)$$. How can we calculate it for every i from 1 to k?
Suppose we have calculated all values of f(j) for some i - 1 and we want to recalculate them for i. The important fact is that these values change (and thus need recalculation) only for the numbers j such that j|i. So if we recalculate only these values f(j) (and each recalculation can be done in O(1) time if we precompute the xn for every $$x \in [1,k]$$), then we will have to do only $$O(k \log k)$$ recalculations overall.