Входные данные
В первой строке записано целое число n (1 ≤ n ≤ 106) — количество элементов массива. Во второй строке через пробел записаны n целых чисел a1, ..., an (1 ≤ ai ≤ 109).
Выходные данные
Выведите остаток от деления S на 108.
Примеры тестов
Входные данные
Входные данные
5
100 1 9 1 3
Входные данные
2
1000000000 1
Примечание
Тесты поделены на несколько групп, но оцениваются отдельно.
-
n, ai ≤ 1000 – 10 баллов
-
n ≤ 5000 – 10 баллов
-
n ≤ 106 ai ≤ 5000 – 30 баллов
-
Без дополнительных ограничений — 50 баллов
Например, если вы решили задачу для n ≤ 5000 и произвольных ai вы получите 20 баллов (первая и вторая группы).