Вам дано n целых чисел a1, a2, ..., an. Обозначим этот список как T.
Пусть f(L) — функция, аргументом которой является непустой список чисел L.
Результатом функции является целое число, вычисленное по следующим правилам:
- Сначала все числа из L дополняются ведущими нулями, чтобы они имели одинаковую длину, равную максимальной длине среди чисел в L.
- Затем строится строка, где символ номер i является минимальным из i-х символов в дополненных нулями исходных числах.
- Полученная строка понимается как число, записанное в десятичной системе счисления, которое и является результатом функции.
Например, f(10, 9) = 0, f(123, 321) = 121, f(530, 932, 81) = 30.
Определим функцию
Здесь
означает подпоследовательность.
Другими словами, G(x) — сумма квадратов сумм элементов непустых подпоследовательностей T, для которых функция f возвращает x, по модулю 1 000 000 007, в конце умноженная на x. Результат последнего умножения не берется по модулю.
Вы хотите вычислить G(0), G(1), ..., G(999 999). Для уменьшения размера вывода вычислите одно число 
, где 
означает побитовое исключающее ИЛИ.
Примечание
В первом примере ненулевые значения G равны: G(121) = 144 611 577, G(123) = 58 401 999, G(321) = 279 403 857, G(555) = 170 953 875. Побитовое исключающее ИЛИ этих чисел равно 292 711 924.
Например, 
, потому что функция f над последовательностями [123] и [123, 555] производит результат 123.
Во втором примере 
В последнем примере 
, где 
— биномиальный коэффициент.