{"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[S] ⊆ #cf_span[T]，若 #cf_span[f(S) = 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":null,"simple_statement":null,"has_page_source":false}