Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

SANDUBA - Sanduíche-íche-íche de atum

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 aiaj 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

Adicionado por:Wanderley Guimarăes
Data:2009-08-31
Tempo limite:0.554s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP JS-RHINO PERL6 PY_NBC SCALA TCL
Origem:Segunda Seletiva para Maratona de Programacao IME-USP - 2008

hide comments
2011-07-21 00:57:15 Kelvin Azevedo Santos [FMUSP]
O skype identificou o ultimo umero do caso de teste como um telefona da polonia:

Call this phone number in Poland with Skype:
+48666666666
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.