Editorial

Problem Author:	Pavlo Tsytsi
Problem Prepared by:	Pavlo Tsytsi
Editorial by:	Pavlo Tsytsi

$(a_{1} + ... + a_{n})^{2} = a_{1}^{2} + ... + a_{n}^{2} + 2 \cdot (a_{1} \cdot a_{2} + ... + a_{1} \cdot a_{n} + a_{2} \cdot a_{3} + ... + a_{2} \cdot a_{n} + ... + a_{n - 1} \cdot a_{n})$ . The part we need is in the second set of parentheses, so all we need is the square of the sum on the segment and the sum of squares on the segment. This can be found using prefix sum. After that, divide by 2 modulo.