Бывают случаи, когда в наборе задач есть очень простая. Эта – одна из них.
Всё, что от вас требуется – вывести сумму всех попарных произведений всех частичных сумм подряд идущих элементов массива длины N по модулю M.
Более понятным языком, если записать все частичные суммы в ряд, то нужно посчитать остаток от деления суммы попарных произведений чисел в этом ряду на M.
Первая строка содержит числа N и M (1 ≤ N ≤ 3·104, 1 ≤ M ≤ 230, M – степень двойки) – количество элементов и модуль.
Во второй строке содержатся N чисел ai (0 ≤ ai ≤ 104) – элементы массива.
В единственной строке выведите число – значение суммы попарных произведений, взятую по модулю M.
2 1024
2 4
44
2 4
2 4
0
3 16
1 2 3
14
В первом примере ответ 44 получается следующим образом: всего имеются 3 частичные суммы – 2, 4, 6 = 2 + 4. 2 * 4 + 4 * 6 + 2 * 6 = 8 + 24 + 12 = 44. Остаток от деления 44 на 1024 равен 44.
