SPOJ Brasil

Os irmãos Ivo Costa e Pedro Costa estão sempre brigando. Tudo é motivo para esta dupla entrar em conflito. A última briga foi por causa de um sanduíche. Os dois estavam em uma festa de casamento e coincidentemente partiram em direção a um mesmo sanduíche de atum. Para tentar remediar a situação, a dona da festa repartiu o pão em duas metades e deu uma metade para cada um dos irmãos. O problema é que o Ivo sentiu-se prejudicado, pois alegou que a metade dada ao Pedro era muito mais recheada que a sua.

Pedimos que você e seus amigos calculem a quantidade de recheio contida no pedaço de sanduíche dado ao Pedro. Para isso, foi preciso que o buffet nos revelasse os segredos de uma de suas receitas mais cobiçadas, o sanduíche de atum: o pão usado é em forma de um quadrado e, portanto, pode ser dividido em N × N subquadrados de tamanhos iguais; em cada subquadrado é colocada uma determinada quantidade de recheio; o gourmet define uma sequência de valores a1, a2, . . . , aN (dados em miligramas) e distribui o recheio no pão da seguinte forma

|a1a1, a1a2 , . . . , a1aN|
|a2a1, a2a2 , . . . , a2aN|
|. . . ,  . . . ,  . . . |
|aNa1, aNa2 , . . . , aNaN|

sendo que a_ia_j corresponde a quantas miligramas de recheio serão colocadas no subquadrado de coordenadas i e j.

Da forma como o corte foi feito, no pão do Pedro tinha os recheios correspondentes aos subquadrados a1a1, a1a2 , . . . , a1aN, mais os recheios correspondentes aos subquadrados a2a2 , a2a3, . . . , a2aN, mais a3a3, a3a4, . . . , a3aN e assim por diante; ou seja, Pedro recebeu os recheios correspondentes à parte triangular superior do pão.

Entrada

A entrada é composta por diversas instâncias. A primeira linha da entrada contém um inteiro T indicando o número de instâncias.

Cada instância é composta de duas linhas. A primeira linha contém um inteiro N indicando o tamanho da sequência. A segunda linha contém N inteiros a1, a2, . . . , aN separados por um espaço.

Restrições

1 <= N <= 100000
0 <= ai <= 100000000 para i = 1, 2, . . . , N

Saída

Para cada instância, imprima a quantidade de recheio que tem no pão do Pedro. Tal valor deve ser impresso módulo 1300031.

Exemplo de entrada

2
4
1 2 3 4
3
666 666 666

Saída para o exemplo de entrada

65
61274