Дана последовательность из N натуральных чисел. Рассматриваются все её непрерывные подпоследовательности длиной не менее пяти элементов, такие что сумма элементов каждой из них кратна k = 117. Найдите количество таких подпоследовательностей.
Входные данные
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 10 000 000). Каждая из следующих N строк содержит одно натуральное число, не превышающее 10 000.
Пример организации исходных данных во входном файле:
9
108
129
143
186
72
195
94
38
69
В данной последовательности условиям удовлетворяют подпоследовательности
129, 143, 186, 72, 195, 94,
186, 72, 195, 94, 38,
72, 195, 94, 38, 69
Поэтому ответ для приведённого примера 3
В ответе укажите два числа: сначала значение искомой суммы для файла А, затем – для файла B.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
