Coprime Arrays

크기가 n인 배열 a에 대해 gcd(a1, a2, ..., an) = 1일 때, 그리고 그럴 때에만 이 배열을 서로소 배열이라고 하자. 여기서 gcd는 인수들의 최대공약수이다.

두 수 n와 k가 주어진다. 각 i (1 ≤ i ≤ k)에 대해, 크기가 n이고 모든 j (1 ≤ j ≤ n)에 대해 1 ≤ aj ≤ i를 만족하는 서로소 배열 a의 수를 구해야 한다. 답은 매우 클 수 있으므로 109 + 7로 나눈 나머지를 계산해야 한다.

첫 번째 줄에는 원하는 배열의 크기와 원소의 최댓값 상한을 각각 나타내는 두 정수 n와 k (1 ≤ n, k ≤ 2·106)이 주어진다.

2·106개의 수를 출력하는 데에는 시간이 많이 걸릴 수 있으므로, 다음과 같은 방식으로 답을 출력해야 한다.

bi를 원소가 $[1, i]$ 범위에 속하는 서로소 배열의 수를 109 + 7로 나눈 나머지라고 하자. 을 109 + 7로 나눈 나머지를 출력해야 한다. 여기서 은 비트 단위 배타적 논리합 연산을 나타낸다(C++ 또는 Java에서는 ^, Pascal에서는 xor).

예제에 대한 설명:

서로소 배열의 수가 많으므로, 서로소 배열이 아니면서 원소가 $[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.