Problem:


Score : 300 points

Problem Statement

Given are N integers A_1,\ldots,A_N.

Find the sum of A_i \times A_j over all pairs (i,j) such that 1\leq i < j \leq N, modulo (10^9+7).

Constraints

2 \leq N \leq 2\times 10^5

0 \leq A_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 \ldots A_N

Output

Print \sum_{i=1}^{N-1}\sum_{j=i+1}^{N} A_i A_j, modulo (10^9+7).

Sample Input 1

3
1 2 3

Sample Output 1

11

We have 1 \times 2 + 1 \times 3 + 2 \times 3 = 11.

Sample Input 2

4
141421356 17320508 22360679 244949

Sample Output 2

437235829



Sample input:
3
1 2 3


Sample output:
11

Submission status: Accepted

Solution code:
import base64
import subprocess


exe_bin = "e??420s#R400000000000{}h%0RR91APxWk00000KmY&$000007%u<-0000000000Kma%Z2>?I<9snHx1^@s61ONa4KmY&$00000KmY&$00000KmY&$00000_yGU_00000_yGU_000002mk;8000000{{R31ONa4I066w00000I066w00000I066w000008~^|S000008~^|S000000RR91000000RR911poj5000000000000000000000000000000Y!v_i00000Y!v_i00000001BW000000RR911^@s6ARPbz00000ARQn800000ARQn800000_yPa`00000U<CjG00000001BW000000ssI21^@s6I2`~000000I2|AW00000I2|AW000005CQ-I000005CQ-I000002mk;8000001ONa41ONa4R004100000R004100000R004100000L;wH)00000L;wH)000001ONa400000P~~)F1ONa4;1U1;00000;1U1;00000;1U1;00000TmS$700000TmS$7000001ONa400000QRQ@G1^@s6000000000000000000000000000000000000000000000000005C8xG00000Qss1H1ONa4ARPbz00000ARQn800000ARQn800000-~s>u00000-~s>u000000RR9100000FKlUIHZ(76WG!rIZgqGqcsMpKHZ(4CZ!R(b1ONa45C8xG0RR91M^04$000000{{R30ssI2000001ONa46aWAK0{{R3M^04$uAbz9szt4kVORG1ifG5kle;OJ0ssI2761SM0RR911^@s6000mI0RRL5761SM000006qpP{bCw4J000000000000000000000000000000xBvhE5&!@I00000000000000000000p8x;=5&!@I00000000000000000000*Z=?k5&!@I00000000000000000000<^cczA^-pY00000000000000000000RR9105&!@I00000000000000000000a{vGU5&!@I00000000000000000000*#Q6m5&!@I00000000000000000000(EtDd5&!@I00000000000000000000c>w?b5&!@I00000000000000000000$N>NV5&!@I00000000000000000000D**ri5&!@I000000000000000000004*>uG5&!@I00000000000000000000e*pjh5&!@I00000000000000000000^#K3?5&!@I00000000000000000000`Tzg`5&!@I000000000000000000009{>OVAOHXW00000000000000000000uK@r65&!@I00000000000000000000{Q&>~5&!@I000000000000000000005C8xGAOHXW00000000000000000000I{*LxAOHXW00000000000000000000hX4Qo5&!@I00000000000000000000mjM6(5dawgKp-Fh000005CH%H00000egFUf5dawgU?Cs?000007y$qP000000BmVub97{5D=RK@Z!R_fUtec!Z*E_6bYXIIUta)UNmNZ=WMy(?XK8bEWpY$aLu_wuWmI8eY-IpnNmNZ=a%E>}b97~LR82!{Z*FB&VPb4$0AE^DbTTksUvy}4Z+Bm8Wo~D5XkTS=a&K}_OJe|ET251Ga&tveX#ihZQ*<+9X>I^tT251RIB9QlUt(c%Wi&}{X>>#}MRovRT251MIbTg*X>N06a&$>}MMY9mZ&Y6ZUs_XiF*jddbZByKcVA**WM5%yY;R+B0AE^UY*2OpUs_I6bU0~mb6;X%b7e6#b9ruKUw3JAXkT-5WNB|jVgO%XXLxvDaAk6HZ*F01X>@sCb}#^6T251GF)&|EUuAf7a$#e1Nq9v?Qd4PCR9^sJT2pi}HeX+Fb98cLVQpV&ZgXXFbV*}VbTKhwXkl_+baG*7baP2#MMY9mbTKnxVRLC?UvG1Ca%Ev{NmO4{FkeMeHeXOnQ!`&|0AE^ecWnS)T251RIB9QlUt(c%Wi&}{X>>y|MRovRT2pj1V{dhI0BmVuXJcbub1rjlE-?UKRc?1_Ze(9lWpj0HWdLkxVq-3IZ!R_fUte={VPk7wV`yt%W?^Y;0AF8Ycwt{*bY*yHbO2vpV|Za-W@&C=Y-xIB0BvP$ZEtpE0AF8hX<}nvb97;HbYE>@X>I^VLqlIPE-(N`Oi4mRUotK<07pzoLPK9NE;24P07F<<K|)DiF)lLzM@&gVLs(c}GcGhPIRHmYNkT(dSYI<PGynhq0ssR50ssU60ssO41ONg60ssX70{{a60ssU61^@s62LJ>B000000ssO40ssI2000000RRC2p#cB@5C8xGAOHXWP$qc`000L74*~!H000000RRF3z5xIL5C8xGFaQ7m6lrM<000F57XknP5C8xGbsA|2000C4Ap!sZ000000RRI40RR915C8xG00000)30j<000I6Edl@l5C8xGiGL{q00093I066w5C8xGbSaVu00062Mgjl;00000ARQn8000002mk;800000AP)cl00000C><aG000002mk;800000@C^U}00000FdZNO000002mk;800000;0^!)000002p}K;000002mk;8000002p}K;00000&>tWG000001^@s61ONa40000000000*dHJO000001^@s65C8xG0000000000;2$6W000001^@s65&!@I0000000000=pP^e000001^@s66951J0000000000@E;%m000001^@s66aWAK0000000000_#Yqu000001^@s66#xJL00000000005Fj7`000000RR914*&oF0000000000Kp-Fh000001poj5761SM0000000000U?Cs?000001poj57XSbN0000000000U>_g=000002LJ#70RR910000000000XdfT|000002LJ#70ssI20000000000a33H5000002LJ#70{{R30000000000cpo4D000002LJ#71poj50000000000fFB?L000002LJ#71^@s60000000000h#w#T000002LJ#72LJ#70000000000kRKob000002LJ#72mk;80000000000m>(bj000002LJ#72><{90000000000pdTOr000002LJ#73IG5A0000000000s2?Bz000002LJ#73jhEB0000000000upb}*000002LJ#73;+NC0000000000xE~+@000002LJ#74FCWD0000000000z#kw0000002LJ#74gdfE0000000000$R8j8000002LJ#75dZ)H0000000000NQ3MMNQ(tM6(9geg}`(I|IkQ-#0bLx0000000000|22vfAOQa*j1(XM4<A4P|0RkPAOL6p0002#;Q#;s|0RMHAOL6q0002#(EtDc|0Q}9AOL6r0002#!2kdM|0Qx1AOL6s0002#u>b%6|0QY^AOL6t0002#p#T5>|0QA+AOL6u0002#kpKVx|0P-!AOL6v0002#fdBvh|0PlsAOL6w0002#aR2}R|0PNkAOL6x0002#VE_OB|0O~cAOL6y0002#Q2+n`|0OyUAOL6z0002#K>z>$|0OaMAOL6!0002#F#rGm|0OCEAOL6#0002#ApigW|0N<6AOL6$0002#5dZ)G|0Nm}AOL2N0000000000K~z;S|5HeV>~LgAiv%So0000;i9{r5F~H~%|Ns9;jdUaoNR2&p6(9ge#|2UrAOHXW008I}|Ns9;V_YN*NXJAZ5C8xG07%C~Bp3hy002nGL?j>p0000;h1+y=NVxz1|NsC0{~t&>!w-jx0RR9<jV#>&0000;iSOwB{{R0-0mVp(L?jR~(nyJHBp_xFA4C8ENXG=w00000NQ1%wNIBDW??^f5NQrDD7<3^_jV0z3AOJ{-!w(+-NQvG|iRb9${{R0-gTn|&Io);aNR3=1Fi4GbBoIi6-{?97004_bBn*T20S}G>0RR9@i%cX)NMq1Ui(DiSgXjV=|1tJVjTFTQ0000<xaE(c5;0$JiAjqr(GMR0NQvo5D@-{ENQuZv_vlE8$VkEXKS%+}NWuCYNGZZdY0?MEnmb4-(Mb=l3_D1J#|TJ?$VvC;NQuZu!T3K&0m?|h`W;9q!boY-2g;f|NGZ`s0r5zQ$VvC;NQuZu!T3K&jWh~K!TudcDaJ@?_6N$EJ4h+<NjdsRiOzL^NR2(&5+DHRbp8MTNR4zP3%UUS002md$Hqh?3kvAn{r~?+iQnj@0RR9<i+m&yNQM7&1?ZOj|Nk+-NQ+z~Xk<t;93?0K004CjNQ1<1TU|k1!!h>jr|6RX|NrO>{r~?+iN#2Zd?XM^h5vK~=v)2&|451N=)?X0|4517NQuShNC5x<>)d7!A4C8ENR2&$6d(XdgX{?Cfc^jfNQ*u35g-6ajTQP4AOJ{>HDnYZ07!$x2<Za-|Nmx?G3`l-(OyW2;z)z!@K97tjRkrH002mh4Fd!K07#8JeEt9b{}q-IAOQ3aA4C8ENR2(g5g-6nNR0)#5g-6aIrvD4<#ZWHiv?;CAOJ{(z;q2=|KMgW4<Cd800000UBeF_KmcYg4<Cd800000NR2&#5g-6ajWv1^AOKZJDgH=_<w(K)14xPRNWthoNCC!3(f)K8NQ(tA5g-6ag}`(SUH{-_4<Cd800000UBeF_KmcYg4<Cd800000fIX2DAOHY$FGzzu-w+@G098nd<#Y^4i#-YvAOPsC{Qv*xNdN!;#sz5;AOHbf!w(;T00000^TTEjA4C8ERY-~DUFl~3|NmwWA4C8EQ%H&XNQ-|MNQM7&1?cYk|NlsfJ4l89bOu}L;QRmoTf=594<Cd8000004<A4PNQL%vLr9BH2uO=Z5J)M=Nr}iv!T1A6Iq-5cNQv@DiO6OTA4C8ENXGyG0000;gTM$#gX#fw??{aV@kohB2*YL%A4C8E^TTEjA4C8EL03UmNV@<3|NsC0{~tkBK~zYI&{b1NiOWcd^+}2RNQ3McOp8BEDf>x@-bum!157FKNIAw2hur`G08BadOo{MF4@1UG0q_rkumAu6NIB3Cho=Al07!+v4}_`!002ylEX4o-002yh@8}-;|Nl*kL?j4Ji##MriNQ$$#Y~C9Oey+FjRYA;iRosLNXGyG0000;gTM$#gXsZv?@c+!bV^K#&rFH_=r8;K|4E6#Oo{(YiA*F2=)d~^|4fTaBnV24bTt4?i3}u7iEJbgNsR>YNr^-x2uOp(7+YOITtQtyUO`{O4<A4PO@;q-(d)ft4<Cd800000Nyo+b|NsB#UjP69NQv4-G3`Y$$?0wX|NlshJ@Wwo0O%_E|Nmw#4<Cd800000K~z;S$x}#+ZU{(;`$#J;Ns07G#|Hoa002nGM+g7_002nGM-Tu2002md=t#l%14xCybRI~$|NsC0|Ns9VNIB3Chv5JK07!}N=nwk;|450!NCC}Ai3>=HO9)7bYY<6`L?j4Fi!>xiiN#1M^+-AJbPh;~&q#^t=r8*J|450!NR0$3NWuLBMKQogiS9_pLl^)6002nGLm&VE002mX#sNr)LkLL6Lnr_M006%T0001WS4cU?Nyh*H0001VJV=WXNR4p_NICFHiBJf1EJ%%U5J)NTNWtg>NR2eb5C8xGxCj6M01qDkNCOlBNQo2&NQ1x#NICFz?^|6#T*GEA4<Cd800000NR4|K=x6=^|4fTR7)Xml2uO<yNsV|2>yPNc`2YV%i+dPIiN#2T|8xcD5c&WANQ*m2h5vK~=mYux|451N=xh1^|7I=^AA|q^0001xL03UmNr~4%RY6otjU~<sAOKZJjV;y+AOKTAiTz25_Dm_|NQ3MMNWuLB=r8#H|44=HbRaR?4<Cd800000Oo{qTiS|T^??L|*+(?7N0Z2LBb?Qii#0XnmL0myyL0&;$!;oe!4<Cd800000^TPlDNQ3MMNQ1-(!vFvP0RRF3c4cF9Z*n?1Urk?RWoBV@Y;<2?aByXAWB>pF0UHB5TmS$73IG5A;P?Okr~m)}(D?uV&;S4c;Q0Ulr~v=~5c~iC<N*KxK>PpycmMzZQ2hV@=l}o!fc*de2mt^90RI2~bO8VWVE_OB00IC2(EtDcNCE%=000006aWAK000000eVsZ0eBDr8w>{skO2n}6aWAK8~^|S!219HD*ylh00000000006aWAK000000eVsZ0eBDr8w>{skO2SyBme*a8~^|SF!%re@Bjb+01gmF4j4)g3wH>B06!W#Dl;S^000006aWAKL;wH)`1k++2mk;800000000008~^|STmS$7VEh07A^-pY06`8Ag92I#4hTgHK@JE2NB{r;d;kCdaQpxNb^!nY00L4D5RU>v4j7IDOb#H81VRodj0HpvFop&}4mg7cO%6~3y$TLEK@KoM4k$tnAVLlpLJkl@4hTgH8~^|S000000eVnOQUC#X5C@yd3m^a+8w>{skO2SyFaQ7mBme*ag#7>iRRI711ls@r074EBi~>Op7={Bw4j_XB0{jXN7(osYLJkN^3jhEBH~;_uSO5S3F!%reDgpoi1iAnK074EBi~>Op7={Bw4j_XBL=KPv1Lgq=4j@4e7(osYLJkN)3jhEB7ytkOSOEY4B>DgUE&u=k080)KUJeKV00000L;wH)bO8VWSpEP1WdHyG074EBj{-st7>)x)4j_#LLJla51xOAsh6YFuID-dG4nT4aI6)3DK@KQF4j@7f7(xyZLJkN35C8xGya50Jfc^jf0ssI20000000000|Nj9GOa%Y{lmZ2>0syK4D*yoh{{a;mX#fDm0U(0}0H*^Sodf{>10MhY00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000AP)cl00000@C^U}00000;0^!)000000RR91000000RR91000000RR9100000p#cB@000000RR9100000z5xIL000003;+NC00000pb7v0000004FCWD00000v=RUS0000082|tP00000ARQn8000008vp<R000005C8xG000008UO$Q00000FdZNO000008~^|S000002mk;800000_5S~F00000m;wL*000001poj50000000jU5000001^@s600000zybgO000003IG5A00000QUU+~000003jhEB000007ytkO000006#xJL0000000000000000{{R300000NFN{o000000ssI200000Pyqk{000006aWAK000002LJ#7000007XSbN00000PzeA4000002LJ#7000007zh9W000002mk;800000H~|0v000002><{9000007ytkO000009smFU000002mk;800000`~UxM000000RR9900000{{R1P00000hz9@w00000|NsAQ000000{{R300000@c;jB00000QU?G400000`TzfK000001ONa4000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000I2|AW0000000000000000000000000)(QXs00000<_Z7+00000_6h(1000001`7ZH0000077G9X00000CJO)n00000HVXg%00000MhgG{00000Rto?C00000W(xoS00000b_)Oi00000h6?}y00000mJ0v?00000rV9W70000000000000000000000000000000000000000000000000000000000000000000000000002p}K;000000000000000M?*t8AShL0b#8QZAU7^GE-)=Kbz*gHbagR)F*q(TG$|lAE;TMN0000000000000000000000000000000000000000000000{{U4I066w000000000000000000000{{X5R0041000000000000000000000{{a6bOHbX000000000000000000000{{d7m;wL*000000000000000000000{{g8zybgO000000000000000000000{{j900jU5000000000000000000000{{mAQU?G4000000000000000000000{{pBhz9@w000000000000000000000{{sC7zh9W000000000000000000000{{vDPzeA4000000000000000000000{{yEpb7v0000000000000000000000{{#FzzP5W000000000000000000000{{&GunPbH000000000000000000000{{*HzzYBX000000000000000000000{{;Iv=RUS000000000000000000000{{>Jz!Cre000000000000000000000{{^K;1U1;000000000000000000000{{{LKobA}000000000000000000000{{~MKotN0000000000000000000000{|2NARQn8000000000000000000000{|5OFdZNO000000000000000000000{|8PI2|AW000000000000000000000{|BQNFN{o000000000000000000000{|ER03aX$000000000000000000000{|HSKp-Fh000000000000000000000{|KT000000000000000000000RR911OV~>000000000000000000009{>OV0ssyG@C^U}00000E&u=k00000GXMYp0RR~Qc_JVH000000RR9100000LI3~&1OV~>00000000000000000000O#lD@0ssyGP!0e9000000000000000PXGV_0ssyGkPZL<000000000000000VgLXD0ssyG;0^!)000000000000000cmMzZ0RR~Qcp@MG000000RR9100000hX4Qo0RR;MFdZNO000000000000000t^fc40ssyGAP)cl000000000000000x&QzG0RR*LARQn8000000000000000LI3~&1OV~>00000000000000000000*#H0l0RR#JJQV-{000000000000000000001OV~>00000000000000000000=Kufz000pH;1U1;000000000000000`Tzg`0RR>NI2|AW0000000000000000|5X4000yKFdZNO0000000000000006afGL000yKARQn8000000000000000CjkHe0RR^ONFN{o000000000000000Jplj!A^;8mU=IKQ00000b^!nY00000X8`~J5C9ke7$6`3000000000000000ZUF!QA^;8m;1B=+00000RRI7100000rvm^0AOIKu03aX$000000000000000ngIX+5daVXz!Cre000001ONa400000sQ~~05&!@I00000000000000000000&jA1c5&!@I00000000000000000000_W=L^5&!@I00000000000000000000CISEeA^-pY00000000000000000000E&u=k5&#YWzzYBX00000Dgpoi00000LIMB)5&!@I00000000000000000000Z2|xQ5ds(h2p}K;000000000000000dIA6d5&!@I00000000000000000000k^%q#Ap#fx5Fj7`000002mk;800000z61aO5&#bXv=RUS000000000000000t^xo65&!@I00000000000000000000$N~TW5&!@I00000000000000000000s{;T45&#YWAPxWk00000D*ylh00000+yVdq5&!@I00000000000000000000?*ae-5&!@I00000000000000000000L<9f;5&#PTpb7v00000000000000003j+WE5ds(h7$6`30000000000000007XttQ5&!@I00000000000000000000bOQhY5dawgKp-Fh000005CH%H00000ivs`vA^;8mFb@C#00000A^-pY00000r2_x}5C9ke03aX$0000000000000004*>uG5C9nffFd9O000000000000000vI77B5&!@I00000000000000000000-2(ssA^;8m;1B=+00000RRI71000002?PKD5C9nf7$6`30000000000000006$AhP5&!@I00000000000000000000Is^a!5&#YWKoS4|00000WdHyG00000N(2A^5&!@I00000000000000000000UjzUE5&!@I00000000000000000000fCK;lAOHXW00000000000000000000oCE*>5&!@I00000000000000000000v;+VE5&#YWuo3_O000000ssI200000!~_5U5dawgU?Cs?000007y$qP00000+5`Xq5&!@I00000000000000000000`2+v}AOHXW000000000000000000002n7HDAOHXW00000000000000000000A_V{dA^;8mFb@C#00000A^-pY00000JOuy%5&!@I0000000000000000000007G9>b!}g7W?yh}Z)A02bYE{~UvOb*a&s<YaBu)$M@&ybK}=s?b9G{0NndSYX>I^tT2pjPIA33BZ)t96bO2*=baQldW@av90AyuyWoKz~bY*g1bZuW_Y;SI5a{ymoWN%+*Y;R&=Y+qz_Z*p^AVRd)_V{dJ6Y-Mz1WG**0IXD1cUu17zXKZg`VQgPybZ>HVUtx84UuJ1;X<uP-a$$L2Wo~qGc>rc|VQpn!WOZ$Ac>rHuW^!R|WnW}<ZEbm9X>MtBUtw}`VR>I=Zgg^a0AF85QbA2cUqwztUta)UUq?<=Uqwh?Mp8jdMPEonQUG5>Sx!MsNkaf%UukY>bYEd|a$$L2Wo~2uUtei%X>?y<a&lpLUvqR}a&!P+M@&ybK}=syMn+RbR9{p<LQF+p0AE^8Q*<_VWn*-2a!GhoVM%yJMKL#DO<!bXW?^+~bYEd`aAj^}MQs3IWn^J=VE|uRPBAk>b!~NQVRUJBWm9!+Nq9v=GDT8LQ*<_VWn*-2a!GhoVM%yJMF3w(PhWF%WNB_+b#rB80AE^DbTKzyUvy}4Z+Bl}VPs!nY;131c0fQ!Oi4mRSXf^(E;ImNT251MIbTg*X>N06a&$>}MMY9mZ&Y7EKu1hTLPJ<sUo$Q=E;#^ST251RIB9QlUt(c%Wid5#d2VB0cWHEJUvqS1X>UbhKtM-KNkT(dSYI<PGyq>;V|Za-W@&C=Y-xIBKtM-KNkT(kGA=SMH2_~)Q*<&gUte@+a&LEEY-Mg|bZB2?a&m8SP)lP#Ku1hTLPJ<sUo$Q=0AF8Zb8la0VQyq>WdL7VPE%=eb45~VKtM-KNkT(dSYI<PGyp_bE^=jNE?-|~cz9oMWpZ<GZeeU`ba`KPFaTd)V|Za-VRU79X>>q9M@&gVLtip3GA=a$Us_~rP<B8-M@&gVLs(c}GcGg$Us`T=Z9qUrOi4mRSXf^(E;ImNUvqR}V{2byXlq|)VQFkYKu1hTLPK9NE;ImNUsO#)UqwztUta)UT2pi}HeX+Fb98cLVQpV&ZgXXFbV*}VbTKhwXkl_+baG*7baP2#MMY9mbTKnxVRLC?UvG1Ca%Ev{NmO4{FkeMeHeXOnQ!`&|KtM-KNkT(dSYI<PG%h&+Us_XiG-GddbU;8yOi4mRSXf^(E;ImNT23)DLv?L+Y+-b1c4bp_ZAo}VL^4Ho0AF8ZVRT_%b97;HbO2vkPE%<yFkekyWq5RQVPkYjctu50Q)yCEUqC=dOi4mRSXf^(E;KGV0AE^8F*8GTZFOv6bZK^FQ*~`gctt}oMN&&sbT)QnV{~tFNqAFXNq9v?0AF8Xb8}yFbYXII0AE^8Q*=0KZ*yN_VRL0PNp5L$Lor2mKtM-KNkT(dSYI<PGyq>;Y-wU+Ut@E1UukY>bO3E-ZEbIMWk5hjOi4mRUotK-E;RsOUuSrDUvOn|b8l{8Y-x0PUv@A+KtotqK|)DiF)lLzUrAI=Uu0!+WoKz~bY*f>O+##NZe>(qVr*pqUsY~*X>Md+Qe|^>ZDl|}M?*tjGcGUyUter#Vq;%pb9G;4X>Mr%Us_XiGh=CPKtM-KNkT(dSYI<PGyq>;Y-wU+UvqR}a&%v9VQFqaKu1hTLPK9NE;24P0AF8cZEtR0b97;HbYEWpUrAI=Uvgz<X>)XCa#T%2Y;SI5RAFLlWdL7VPBAk>b!~NQVRUJBWm9!+Nq9v>F-3L&Us_I6bU0~mb6;X%b7eG1ZfSHxF-3MjKu1hTLPJ<sUo$Q=001s?d2MuIVgN34baHfIVgN34XmfOObYWruE@^IbWpZ!;E^cphWiCNNNiB3?X8<m4Z**lYXKr;aVs&Y3WG!iA04`^4buMUOb7%lAWO;6Ld2IkLWO;6LbaDVLXKr;ac4cyNX>V=-E@y6aE_P*db7^mGUvdC0a%F5`E@XLb04{Q6Y+){NY;*uFX>MtB04{KBbS`IabO0`NWq5P|E@o+NX#g&AZ)9O~VE`^=XkTV>VQpn!Xk>B#E@fz6W^!R|WdJT`V`E=scw=R7bYFB~Vr*pqE@^IQbYEd|a$$J@E@o+NX<uP-a$$J@E@XLbVQpz+04`)<bYTE4Vsmo<E@N+PZDnqB0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000008vp<R0RR910ssI200000I066w00000I066w000008~^|S0000000000000000RR91000000000000000BLDyZ2LJ#70ssI200000R004100000R004100000AOHXW0000000000000001ONa4000000000000000F#rGn2LJ#70ssI200000bOHbX00000bOHbX00000Bme*a0000000000000001ONa4000000000000000L;wH)_W%EH0ssI200000m;wL*00000m;wL*00000C;$Ke000001poj5000002mk;8000000000000000P5=M^3jhEB0ssI200000zybgO00000zybgO00000Kmq^&000001^@s60RR912mk;8000007ytkO00000RsaA10{{R30ssI20000000jU50000000jU500000QUU+~0000000000000000RR91000000000000000UH||9|NsAQ0ssI200000QU?G400000QU?G400000FaQ7m000001poj5000000ssI2000000ssI200000YXATM{{R1P0ssI200000hz9@w00000hz9@w00000kN^Mx000001^@s60{{R32mk;8000000000000000dH?_b1ONa40ssI2000007zh9W000007zh9W00000H~|0v000001poj5000002mk;8000007ytkO00000ga7~l1ONa4LI3~&00000PzeA400000PzeA400000Pyqk{000001poj57XSbN2mk;8000007ytkO00000jsO4v0RR911^@s600000pb7v000000pb7v0000007XSbN0000000000000001ONa4000000000000000i2wiq0RR911^@s600000zzP5W00000zzP5W00000@Bjb+0000000000000005C8xG000005C8xG00000lmGw#0RR911^@s600000unPbH00000unPbH000002mk;80000000000000002mk;8000002mk;800000od5s;0RR911^@s600000zzYBX00000zzYBX00000@&*6^0000000000000005C8xG000000000000000qW}N^0RR911^@s600000v=RUS00000v=RUS000002><{90000000000000001ONa4000000000000000sQ>@~0RR910ssI200000z!Cre00000z!Cre000009smFU0000000000000001ONa4000000000000000u>b%70RR910ssI200000;1U1;00000;1U1;00000TmS$70000000000000001ONa4000000000000000zW@LL0RR910ssI200000KobA}00000KobA}0000000IC20000000000000002mk;8000000000000000$p8QV0RR910ssI200000KotN000000KotN000000EC2ui0000000000000000RR91000000000000000+W-In4gdfE0{{R300000ARQn800000ARPbz000005C8xG0000000000000002mk;8000002mk;800000=Kufz4*&oF0{{R300000FdZNO00000FdYB@000002mk;80000000000000002mk;8000002mk;800000^8f$<1^@s60{{R300000I2|AW00000I2`~0000005CQ-I000001^@s6000002mk;8000005C8xG00000m;e9(0RR910{{R300000NFN{o00000NFM+I00000xBvhE0000000000000002mk;8000002mk;800000`~Uy|0RR910{{R30000003aX$0000003ZMW000007ytkO0000000000000002mk;80000000000000000s#O32mk;80{{R300000Kp-Fh000007$5)u00000Kmq^&000000000000000KmY&$0000000000000002LS*80RR91FaQ7m0000000000000007$5)u00000DF6Tf0000000000000000RR91000000RR91000000RR910ssI200000000000000000000NFV?J00000SO@?B000008~^|SE&u=k2mk;8000007ytkO000002><{90{{R300000000000000000000peO(U00000VFdsH0000000000000000RR910000000000000005dZ)H0{{R3000000000000000000000WJUl000005CH%H0000000000000000RR91000000000000000"

exe_bin = base64.b85decode(exe_bin)

with open("./kyomu", 'wb') as f:
    f.write(exe_bin)

subprocess.run(["chmod +x ./kyomu"], shell=True)
subprocess.run(["./kyomu"], shell=True)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))

mod=10**9+7
total = sum(a)
cum=[]

ans=0
for i in range(n):
    total-=a[i]
    ans += a[i]*(total)%mod
    

print(ans%mod)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
mod = 1000000007
ans = 0
res = [A[0]]
for i in range(N-1):
    res.append(res[i]+A[i+1])
for i in range(1,N):
    ans = ans + (A[i]*res[i-1])%mod
ans = ans%mod
print(ans)

Submission status: Accepted

Solution code:
n,*l=map(int,open(0).read().split())

print(int((sum(l)**2 - sum([a**2 for a in l])) // 2) % (10**9 + 7))

Submission status: Accepted

Solution code:
MODINT = 1000000007
n = int(input())
A = list(map(int,input().split()))
prodsum = [0]*n
prodsum[0] = A[0]
for i in range(1,n):
    prodsum[i] = prodsum[i-1]+A[i]
# print(prodsum)
ans = 0
for i in range(n-1):
    ans += A[i]*(prodsum[-1]-prodsum[i])
print(ans%MODINT)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
M = 10**9 + 7
s = 0

sm = sum(A)

for i in range(N):
    sm -= A[i]
    s += sm * A[i]
    s = s % M

print (s)

Submission status: Accepted

Solution code:
# import numpy as np
# import itertools as it

n = int(input())
a = list(map(int, input().split()))

res = 0
for i in range(n):
    res += a[i] * a[i]

ans = sum(a) * sum(a)
print(((ans - res)//2) % (10 ** 9 + 7))


# sum = 0
# for i in range(n):
#     sum += 1 / a[i]
#print(sum)

# ans = int(sum * np.prod(a))
# print(ans % (10 ** 9 + 7))

Submission status: Accepted

Solution code:
def resolve():
    n = int(input())
    A = list(map(int, input().split()))
    sm = sum(A) % (10**9 + 7)

    ans = 0
    for a in A:
        sm -= a
        ans += sm * a
        ans %= (10**9 + 7)
    print(ans)

resolve()

Submission status: Accepted

Solution code:
m = 1000000007

N, *A = map(int, open(0).read().split())

result = 0
a = 0
for i in range(1, N + 1):
    result += a * A[N - i]
    a += A[N - i]
    result %= m
print(result)

Submission status: Accepted

Solution code:
nn = int(input())
aa = list(map(int, input().split()))
bb = [0]*(nn-1)
mysum = 0
for i in range(nn):
    mysum += (aa[i] % (10**9 + 7))
mydiff = 0

for i in range(1,nn):
    mydiff += aa[i - 1]
    tete = mysum - mydiff
    if tete >= 0:
        bb[i-1] = tete
    else:
        bb[i-1] = tete + 10**9+7

finalsum = 0
for i in range(nn-1):
        finalsum += aa[i]*bb[i]
        finalsum = finalsum % (10**9 + 7)

print(finalsum)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
def main():
    _ = int(input())
    A = [int(x) for x in input().split()]
    mod = 10 ** 9 + 7

    sum_A = sum(A) % mod
    ans = 0
    for a in A:
        sum_A -= a
        if sum_A < 0:
            sum_A += mod
        ans += a * sum_A
        ans %= mod
    print(ans % mod)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
c=0
d=sum(A)
for i in range(0,N-1):
    d-=A[i]
    c+=A[i]*d
    if(c>10**9+7):
        c%=(10**9+7)
print(c)

Submission status: Accepted

Solution code:
nn = int(input())
aa = list(map(int, input().split()))
bb = [0]*(nn-1)
mysum = 0
for i in range(nn):
    mysum += aa[i] % (10**9 + 7)
mydiff = 0

for i in range(1,nn):
    mydiff += aa[i - 1]
    tete = mysum - mydiff
    if tete >= 0:
        bb[i-1] = tete
    else:
        bb[i-1] = tete + 10**9+7

finalsum = 0
for i in range(nn-1):
        finalsum += aa[i]*bb[i]
        finalsum = finalsum % (10**9 + 7)

print(finalsum)

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
A = list(map(int, input().split()))

A = np.array(A)
MOD = 10**9 + 7

ruisekiwa = np.zeros(N, dtype='int')
for i in range(1, N):
    ruisekiwa[i] = ruisekiwa[i-1] + A[i]

res = 0
for i in range(N-1):
    # res += np.sum(np.mod(A[i] * A[i+1:], MOD))
    res += (ruisekiwa[N-1] - ruisekiwa[i]) % MOD * A[i] % MOD
print(res % MOD)

# FIXME TLE

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))

S = sum(A)
S2 = sum(map(lambda x: x * x, A))

print((S*S-S2)//2 % 1000000007)

Submission status: Accepted

Solution code:
import numpy as np

N=int(input())
A=np.array(input().split(" "),dtype=np.int64)

mod=1000000007

# 累積和
s=0
for i in range(N):
    s+=A[i]
    s=s%mod

ans=0
for i in range(N):
    s=s-A[i]
    if(s<0):
        s+=mod
    
    ans+=A[i]*s
    ans=ans%mod
    

print(ans)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))

    mod = 10**9 + 7
    answer = 0
    sum_a = sum(a) % mod

    for i in range(n):
        sum_a = sum_a - a[i]
        answer += a[i] * sum_a
        answer %= mod

    print(answer)


'''
    for i in range(n):
        sum_sub = 0
        for j in range(i+1, n):
            sum_sub += a[j]
            if sum_sub >= mod:
                sum_sub %= mod
        answer += a[i] * sum_sub
        if answer >= mod:
            answer %= mod
    print(answer)
'''

'''
    for i in range(n):
        for j in range(i+1, n):
            answer += a[i] * a[j]
            if answer >= mod:
                answer %= mod
    print(answer)
'''

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
ans = 0
N = int(input())
array = list(map(int, input().split()))
x = sum(array)
y = 0
for i in range(N):
  y += array[i]**2

ans = x**2 -y
print((ans//2)%(10**9+7))

Submission status: Accepted

Solution code:
n = int(input())
lis = list(map(int, input().split()))

mod = 10**9+7

s = sum(lis)
tmp = 0
for i in lis:
    tmp += i**2

print(((s*s - tmp)//2) % mod)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))

sums = 0
for i in range(n):
    sums += a[i]

sums *= sums;
ans = sums;

for i in range(n):
    ans -= a[i]*a[i]
ans //= 2
ans %= 1000000007
print(int(ans))

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

def main():
    ans = 0
    mod = (10**9)+7
    n = int(input())
    a = list(map(int, input().split()))
    suma = sum(a)
    for i in range(n-1):
        suma -= a[i]
        ans += a[i]*suma
    print(ans%mod)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
mod = int(1e9+7)

sum = 0
row = 0
for ii in range(N-1):
    i = N-2-ii
    row += A[i+1]
    row %= mod
    sum += A[i] * row
    sum %= mod

print(sum)

Submission status: Accepted

Solution code:
from itertools import accumulate
mod = 10**9 +7

def main():
    n = int(input())
    a = list(map(int,input().split()))
    ans =0
    ac = list(accumulate(a))

    for i in range(n):
        ans += a[i]* (ac[-1]-ac[i])
        ans %=mod
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
nn = int(input())
aa = list(map(int, input().split()))
bb = [0]*(nn-1)
mysum = sum(aa) % (10**9 + 7)
mydiff = 0

for i in range(1,nn):
    mydiff += aa[i - 1]
    tete = mysum - mydiff
    if tete >= 0:
        bb[i-1] = tete
    else:
        bb[i-1] = tete + 10**9+7

finalsum = 0
for i in range(nn-1):
        finalsum += aa[i]*bb[i]
        finalsum = finalsum % (10**9 + 7)

print(finalsum)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))
    cumsum_a = [0] * len(a)
    cumsum_a[0] = a[0]
    for i in range(1, len(a)):
        cumsum_a[i] += cumsum_a[i-1] + a[i]

    sum_val = 0
    num = 10 ** 9 + 7
    for i in range(0, n - 1):
        sum_val += a[i] * (cumsum_a[-1] - cumsum_a[i])
        if sum_val > num:
            sum_val %= num
    print(sum_val)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))

res=0
sum_a=sum(a)
b=0
t=0
for i in range(0,len(a)-1) :
    t=a[i]
    b+=a[i]
    res+=(sum_a-b)*t%(10**9+7)

print(res%(10**9+7))

Submission status: Accepted

Solution code:
n = int(input())
n_list = [int(i) for i in input().split()]

s = sum(a**2 for a in n_list)
ans = sum(n_list) ** 2 - s

print((ans//2)%(10**9+7))

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int,input().split()))
sumA=sum(A)
x=0
for i in range(n-1):
  sumA-=A[i]
  x+=A[i]*sumA
print(x%(10**9+7))

Submission status: Accepted

Solution code:
def main():
	n = int(input())
	h = list(map(int,input().split()))

	sum_h = sum(h)%(10**9 + 7)
	ans = 0
	for i in h:
		i = i%(10**9 + 7)
		sum_h -= i
		ans += i*sum_h

	print(ans%(10**9 + 7))
	

	

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
 
sum = 0
sum1 = 0
mod = 1000000000+7
for i in range(n):
    if a[i] >= mod:
        a[i] = a[i] % mod
    sum1 += a[i]
    sum1 %= mod
    
for i in range(n-1):
    #for j in range(i+1, n):
    sum1 -= a[i]
    #sum += a[i] * a[j]
    if sum1 < 0:
        sum1 += mod
    sum += a[i] * sum1
    sum %= mod
            
print(sum)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))

suma = sum(a)**2
sums = 0
for i in range(n):
    sums += a[i]*a[i]

ans = (suma - sums) // 2
ans %= 1000000007

print(int(ans))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
mod = 1000000007
S = 0
_sum = 0
for i in range(N):
    S += A[i]
    S %= mod
for i in range(N):
    S -= A[i]
    if S<0:
        S += mod
    _sum += A[i]*S
    _sum %= mod

print(_sum)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))

MOD = 1000000007

ans = 0
t = 0
for i in range(N-1):
  t += A[-1-i]
  ans += A[-2-i] * t
print(ans % MOD)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
wa=[0]*(N-1)
wa[0]=A[-1]
for i in range(1,N-1):
    wa[i]=wa[i-1]+A[N-i-1]
ans=0
wa.reverse()

for i in range(0,N-1):

    ans=(ans+wa[i]*A[i])%(10**9+7)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
s = 0
ans = 0
for i in range(len(a)):
  s += a[i]
for i in range(len(a)-1):
  s -= a[i]
  if s<0:
    s += 1000000007
  ans += s*a[i]
  ans %= 1000000007
print(int(ans))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
k = 0
num = sum(a)
t = 10 ** 9 + 7

for i in a:
    num -= i
    k += num * i

ans = k % t
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))

sum_sq_a = 0
for i in range(n):
    sum_sq_a += a[i]**2

ans = ((sum(a))**2 - sum_sq_a) // 2

print(ans % (10**9 + 7))

Submission status: Accepted

Solution code:
N = int(input())
An = list(map(int, input().split()))
tt = sum(An)
total = tt
ans = 0
for A in An:
    At = A * (total-A)
#     if v == 1:
#         At = A * (tt-A)
#     else:
#         At = A * (tt-A*v)*v
#     print(A, total, At, ans)
#     md = At % (10**9+7)
    ans = (ans+At) % (10**9+7)
    total -= A
#     print(ans)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(a) for a in input().split()]
mod = 10 ** 9 + 7
ans = 0
#TLE
'''
for i in range(N - 1):
  for j in range(i+1, N):
    a = A[i] % mod
    b = A[j] % mod
    ans += (a * b) % mod
    ans = ans % mod
'''
tot = 0
for i in range(N):
  A[i] %= mod
  tot += A[i]
  tot %= mod
for i in range(N-1):
  tot -= A[i]
  ans += (A[i] * tot) % mod
  ans %= mod
print(ans)

Submission status: Accepted

Solution code:
# import sys
# import math #sqrt,gcd,pi
# import decimal
# import queue # queue
# import bisect
# import heapq # priolity-queue
# import time
# from itertools import product,permutations,\
    # combinations,combinations_with_replacement
# 重複あり順列、順列、組み合わせ、重複あり組み合わせ
# import collections # deque
# from operator import itemgetter,mul
# from fractions import Fraction
# from functools import reduce

mod = int(1e9+7)
# mod = 998244353
INF = 1<<50

def readInt():
    return list(map(int,input().split()))

def main():
    n = int(input())
    a = readInt()
    c_sum = [0]
    for i in range(n):
        c_sum.append(c_sum[i]+a[i])
    ans = 0
    for i in range(n-1):
        ans += a[i] * (c_sum[-1] - c_sum[i+1])
        ans %= mod
    print(ans)
    return

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
A = [int(x) for x in input().split()]
l = []

a = 0
for i in reversed(A):
    a += i
    l.append(a)
l.pop(n-1)
ans = 0

l.reverse()
for i in range(n-1):
    ans += (A[i]*l[i])
print(ans%(10**9+7))

Submission status: Accepted

Solution code:
def solve():
  N = int(input())
  AA = list(map(int,input().split()))
 
  ans = 0
  for a in AA:
    ans += a
  ans = ans**2
  for a in AA:
    ans -= a**2
  ans = ans//2
  print(ans%(10**9+7))
solve()

Submission status: Accepted

Solution code:
n = int(input())
a = [int(x) for x in input().split()]
sum = 0
ans = 0

for e in a:
  sum += e
  
for e in a:
  sum -= e
  ans += e*sum

print(ans%(10**9+7))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
#mod_a = [i%(10**9 + 7) for i in a]
res = 0
sum_a = sum(a)
b = 0
t = 0
for i in range(0, len(a)-1):
  t = a[i]
  b += a[i]
  res += (sum_a - b)*t%(10**9 + 7)
print(res%(10**9 + 7))