Çàäà÷à . Ðàçíîñòè

Ó Äæîíà Äîó åñòü ìàññèâ a èç n ýëåìåíòîâ. Äæîí õî÷åò íàéòè âåëè÷èíó , òî åñòü ñóììó êâàäðàòîâ ðàçíîñòåé ýëåìåíòîâ ìàññèâà ïî âñåì âîçìîæíûì ïàðàì i, j.

Íàïðèìåð äëÿ ìàññèâà {1, 2, 3} òàêàÿ âåëè÷èíà áóäåò ðàâíà (1 - 1)2 + (1 - 2)2 + (1 - 3)2 + (2 - 1)2 + (2 - 2)2 + (2 - 3)2 + (3 - 1)2 + (3 - 2)2 + (3 - 3)2 = 0 + 1 + 4 + 1 + 0 + 1 + 4 + 1 + 0 = 12

Íàéäèòå îñòàòîê îò äåëåíèÿ S íà 10⁸.

Íàïîìíèì, êàê ðàáîòàòü ñ îñòàòêàìè îò äåëåíèÿ. Îñòàòîê îò äåëåíèÿ ÷èñëà a íà ÷èñëî b îáîçíà÷èì êàê . Âåðíû ñëåäóþùèå ñîîòíîøåíèÿ:

• 
• 
• (äëÿ a ≥ b).

Ê ïðèìåðó, âû õîòèòå ïîñ÷èòàòü âåëè÷èíó . Ïåðåìíîæèòü ýòè òðè ÷èñëà â ñòàíäàðòíîì òèïå äàííûõ âàì íå óäàñòñÿ, íî ìîæíî âîñïîëüçîâàòüñÿ ïåðâûì ñîîòíîøåíèåì è ïîñ÷èòàòü ñíà÷àëà Òåïåðü ìîæíî ïåðåìíîæèòü ïîëó÷èâøååñÿ ÷èñëî è 107 + 3 è ïîëó÷èòü .

 ïåðâîé ñòðîêå çàïèñàíî öåëîå ÷èñëî n (1 ≤ n ≤ 10⁶) — êîëè÷åñòâî ýëåìåíòîâ ìàññèâà. Âî âòîðîé ñòðîêå ÷åðåç ïðîáåë çàïèñàíû n öåëûõ ÷èñåë a1, ..., an (1 ≤ a_i ≤ 10⁹).

Âûâåäèòå îñòàòîê îò äåëåíèÿ S íà 10⁸.

Âõîäíûå äàííûå

3
1 2 3

12

5
100 1 9 1 3

74928

2
1000000000 1

2

Òåñòû ïîäåëåíû íà íåñêîëüêî ãðóïï, íî îöåíèâàþòñÿ îòäåëüíî.

• n, a_i ≤ 1000 – 10 áàëëîâ
• n ≤ 5000 – 10 áàëëîâ
• n ≤ 10⁶ a_i≤ 5000 – 30 áàëëîâ
• Áåç äîïîëíèòåëüíûõ îãðàíè÷åíèé — 50 áàëëîâ

Íàïðèìåð, åñëè âû ðåøèëè çàäà÷ó äëÿ n ≤ 5000 è ïðîèçâîëüíûõ a_i âû ïîëó÷èòå 20 áàëëîâ (ïåðâàÿ è âòîðàÿ ãðóïïû).