{"raw_statement":[{"iden":"statement","content":"You are given _n_ integers _a_1, _a_2, ..., _a__n_. Denote this list of integers as _T_.\n\nLet _f_(_L_) be a function that takes in a non-empty list of integers _L_.\n\nThe function will output another integer as follows:\n\n*   First, all integers in _L_ are padded with leading zeros so they are all the same length as the maximum length number in _L_.\n*   We will construct a string where the _i_\\-th character is the minimum of the _i_\\-th character in padded input numbers.\n*   The output is the number representing the string interpreted in base 10.\n\nFor example _f_(10, 9) = 0, _f_(123, 321) = 121, _f_(530, 932, 81) = 30.\n\nDefine the function\n\nHere, denotes a subsequence.In other words, _G_(_x_) is the sum of squares of sum of elements of nonempty subsequences of _T_ that evaluate to _x_ when plugged into _f_ modulo 1 000 000 007, then multiplied by _x_. The last multiplication is not modded.\n\nYou would like to compute _G_(0), _G_(1), ..., _G_(999 999). To reduce the output size, print the value , where denotes the bitwise XOR operator."},{"iden":"input","content":"The first line contains the integer _n_ (1 ≤ _n_ ≤ 1 000 000) — the size of list _T_.\n\nThe next line contains _n_ space-separated integers, _a_1, _a_2, ..., _a__n_ (0 ≤ _a__i_ ≤ 999 999) — the elements of the list."},{"iden":"output","content":"Output a single integer, the answer to the problem."},{"iden":"examples","content":"Input\n\n3\n123 321 555\n\nOutput\n\n292711924\n\nInput\n\n1\n999999\n\nOutput\n\n997992010006992\n\nInput\n\n10\n1 1 1 1 1 1 1 1 1 1\n\nOutput\n\n28160"},{"iden":"note","content":"For the first sample, the nonzero values of _G_ are _G_(121) = 144 611 577, _G_(123) = 58 401 999, _G_(321) = 279 403 857, _G_(555) = 170 953 875. The bitwise XOR of these numbers is equal to 292 711 924.\n\nFor example, , since the subsequences \\[123\\] and \\[123, 555\\] evaluate to 123 when plugged into _f_.\n\nFor the second sample, we have\n\nFor the last sample, we have , where is the binomial coefficient."}],"translated_statement":[{"iden":"statement","content":"你被给定 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]。记这个整数列表为 #cf_span[T]。\n\n定义函数 #cf_span[f(L)]，它接受一个非空整数列表 #cf_span[L]。\n\n该函数将输出另一个整数，如下所示：\n\n例如 #cf_span[f(10, 9) = 0]，#cf_span[f(123, 321) = 121]，#cf_span[f(530, 932, 81) = 30]。\n\n定义函数 \n\n换句话说，#cf_span[G(x)] 是所有非空子序列的平方和之和，这些子序列在代入 #cf_span[f] 后结果为 #cf_span[x]，结果对 #cf_span[1 000 000 007] 取模，然后再乘以 #cf_span[x]。最后一次乘法不取模。\n\n你希望计算 #cf_span[G(0), G(1), ..., G(999 999)]。为减少输出大小，请输出这些值的异或和，其中  表示按位异或运算符。\n\n第一行包含整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 1 000 000]) —— 列表 #cf_span[T] 的大小。\n\n第二行包含 #cf_span[n] 个空格分隔的整数 #cf_span[a1, a2, ..., an] (#cf_span[0 ≤ ai ≤ 999 999]) —— 列表的元素。\n\n输出一个整数，即问题的答案。\n\n对于第一个样例，#cf_span[G] 的非零值为 #cf_span[G(121) = 144 611 577]，#cf_span[G(123) = 58 401 999]，#cf_span[G(321) = 279 403 857]，#cf_span[G(555) = 170 953 875]。这些数的按位异或等于 #cf_span[292 711 924]。\n\n例如，，因为子序列 #cf_span[[123]] 和 #cf_span[[123, 555]] 在代入 #cf_span[f] 时结果为 #cf_span[123]。\n\n对于第二个样例，我们有 \n\n对于最后一个样例，我们有 ，其中  是二项式系数。"},{"iden":"input","content":"第一行包含整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 1 000 000]) —— 列表 #cf_span[T] 的大小。第二行包含 #cf_span[n] 个空格分隔的整数 #cf_span[a1, a2, ..., an] (#cf_span[0 ≤ ai ≤ 999 999]) —— 列表的元素。"},{"iden":"output","content":"输出一个整数，即问题的答案。"},{"iden":"examples","content":"输入3123 321 555输出292711924输入1999999输出997992010006992输入101 1 1 1 1 1 1 1 1 1输出28160"},{"iden":"note","content":"对于第一个样例，#cf_span[G] 的非零值为 #cf_span[G(121) = 144 611 577]，#cf_span[G(123) = 58 401 999]，#cf_span[G(321) = 279 403 857]，#cf_span[G(555) = 170 953 875]。这些数的按位异或等于 #cf_span[292 711 924]。例如，，因为子序列 #cf_span[[123]] 和 #cf_span[[123, 555]] 在代入 #cf_span[f] 时结果为 #cf_span[123]。对于第二个样例，我们有 对于最后一个样例，我们有 ，其中  是二项式系数。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $, $ T = (a_1, a_2, \\dots, a_n) $ with $ a_i \\in \\{0, 1, \\dots, 999999\\} $.  \nLet $ f(L) $ be a function on non-empty subsequences $ L \\subseteq T $, defined as:  \n$$\nf(L) = \\left| \\sum_{x \\in L} x - \\sum_{x \\in L} \\text{reverse}(x) \\right|\n$$  \nwhere $ \\text{reverse}(x) $ denotes the integer formed by reversing the decimal digits of $ x $ (e.g., $ \\text{reverse}(123) = 321 $, $ \\text{reverse}(530) = 35 $).\n\nLet $ G(x) $ be defined for $ x \\in \\{0, 1, \\dots, 999999\\} $ as:  \n$$\nG(x) = x \\cdot \\left( \\sum_{\\substack{L \\subseteq T \\\\ L \\neq \\emptyset \\\\ f(L) = x}} \\left( \\sum_{y \\in L} y \\right)^2 \\right)\n$$  \n(Only the sum of squares is taken modulo $ 10^9 + 7 $; the final multiplication by $ x $ is not modded.)\n\n**Constraints**  \n1. $ 1 \\le n \\le 10^6 $  \n2. $ 0 \\le a_i \\le 999999 $ for all $ i $\n\n**Objective**  \nCompute:  \n$$\n\\bigoplus_{x=0}^{999999} G(x)\n$$  \nwhere $ \\oplus $ denotes bitwise XOR.","simple_statement":null,"has_page_source":false}