{"raw_statement":[{"iden":"statement","content":"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.\n\nYou 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."},{"iden":"input","content":"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."},{"iden":"output","content":"Since printing 2·106 numbers may take a lot of time, you have to output the answer in such a way:\n\nLet _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)."},{"iden":"examples","content":"Input\n\n3 4\n\nOutput\n\n82\n\nInput\n\n2000000 8\n\nOutput\n\n339310063"},{"iden":"note","content":"Explanation of the example:\n\nSince the number of _coprime_ arrays is large, we will list the arrays that are non-coprime, but contain only elements in range \\[1, _i_\\]:\n\nFor _i_ = 1, the only array is coprime. _b_1 = 1.\n\nFor _i_ = 2, array \\[2, 2, 2\\] is not coprime. _b_2 = 7.\n\nFor _i_ = 3, arrays \\[2, 2, 2\\] and \\[3, 3, 3\\] are not coprime. _b_3 = 25.\n\nFor _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."}],"translated_statement":[{"iden":"statement","content":"我们称一个大小为 $n$ 的数组 $a$ 为 _互质_ 的，当且仅当 $\\gcd(a_1, a_2, ..., a_n) = 1$，其中 $\\gcd$ 表示参数的最大公约数。\n\n给定两个数 $n$ 和 $k$。对于每个 $i$（$1 ≤ i ≤ k$），你需要确定满足以下条件的 _互质_ 数组 $a$ 的数量：数组大小为 $n$，且对每个 $j$（$1 ≤ j ≤ n$）都有 $1 ≤ a_j ≤ i$。由于答案可能非常大，你需要对 $10^9 + 7$ 取模计算。\n\n第一行包含两个整数 $n$ 和 $k$（$1 ≤ n, k ≤ 2·10^6$），分别表示目标数组的大小和元素的最大上界。\n\n由于输出 $2·10^6$ 个数字可能耗时很长，你必须以如下方式输出答案：\n\n设 $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_）。"},{"iden":"input","content":"第一行包含两个整数 $n$ 和 $k$（$1 ≤ n, k ≤ 2·10^6$），分别表示目标数组的大小和元素的最大上界。"},{"iden":"output","content":"由于输出 $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_）。"},{"iden":"examples","content":"输入\n3 4\n输出\n82\n\n输入\n2000000 8\n输出\n339310063"},{"iden":"note","content":"示例解释：\n由于 _互质_ 数组的数量很大，我们将列出非互质但元素仅在范围 $[1, i]$ 内的数组：\n\n当 $i = 1$ 时，唯一的数组是互质的。$b_1 = 1$。\n\n当 $i = 2$ 时，数组 $[2, 2, 2]$ 不是互质的。$b_2 = 7$。\n\n当 $i = 3$ 时，数组 $[2, 2, 2]$ 和 $[3, 3, 3]$ 不是互质的。$b_3 = 25$。\n\n当 $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$。"}],"sample_group":[],"show_order":[],"formal_statement":"Let $ n, k \\in \\mathbb{N} $, with $ 1 \\leq n, k \\leq 2 \\cdot 10^6 $.\n\nFor each $ i \\in [1, k] $, define:\n\n- $ A_i = \\{ \\mathbf{a} \\in [1, i]^n \\mid \\gcd(a_1, a_2, \\dots, a_n) = 1 \\} $\n- $ b_i = |A_i| \\mod (10^9 + 7) $\n\nCompute:\n\n$$\n\\bigoplus_{i=1}^{k} b_i\n$$\n\nwhere $ \\oplus $ denotes the bitwise XOR operation.","simple_statement":null,"has_page_source":false}