7. Слепое множество

Послать решение | Найти в тренировках

У Паши есть свое мнение насчет того, как надо проводить свободное время. Сегодня он подготовил N карточек, на каждой из которых написал некоторое целое неотрицательное число A_i, после чего он положил все эти карточки в мешок.

Также у Паши есть изначально пустое множество целых чисел S.

До тех пор, пока в мешке есть хотя бы одна карточка, Паша будет тянуть карточки по одной из мешка и добавлять написанное на карточке число во множество S только в том случае, если после добавления этого числа множество S останется понятным. Все порядки вытягивания карточек можно считать равновероятными.

Множество называется понятным, если в нем нету двух таких чисел, что для некоторого разряда десятичной записи в обоих этих числах находится цифра отличная от нуля. Например, множества {0, 10, 203, 5000}, {1337} и {5, 30} являются понятными, а множества {5, 11, 300} и {5, 6} — не являются.

После того, как Паша достал все карточки из мешка, он подсчитывает сумму элементов полученного множества S.

Паше стало интересно, чему равняется значение математического ожидания суммы элементов множества S. Сам он, конечно, не может посчитать это значение.

Ваша задача — попытаться написать программу, которая посчитает искомое значение математического ожидания.

Входные данные

Первая строка входных данных содержит целое число N — количество карточек в мешке (1 ≤ N ≤ 2 · 10⁵).

Во второй строке входных данных содержится N целых чисел A_i — числа, которые были записаны на карточках (0 ≤ A_i ≤ 10¹⁵).

Выходные данные

В единственной строке выходных данных выведите вещественное значение искомого математического ожидания.

Относительная или абсолютная погрешность этого значения не должна превышать 10⁻⁶.

Примеры