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

QUADRA13 - Quadradinho de 8

 

Fernando ficou sabendo de um novo jogo chamado quadradinho de 8. Nesse jogo, é apresentado ao jogador uma fileira de quadrados, um do lado do outro. Em cada quadrado há um número escrito. Veja abaixo um exemplo de fileira de quadrados:

Para ganhar, o jogador deve escolher alguns quadrados de forma que eles juntos formem apenas um retângulo contíguo e que a soma de seus números seja divisível por 8. Na fileira de quadrados acima, o jogador ganha se escolher os quadrados com os números 6, 0 e 2. O jogador perde se escolher os quadrados com 3, 4 e 9, apesar da soma ser divisivel por 8, os quadrados não estão juntos, eles acabam formando dois retângulos separados.

Você deve estar pensando agora que Fernando quer sua ajuda para que você mostre a ele como ganhar o jogo, mas Fernando é um garoto muito esperto e sabe resolver o jogo rapidamente. Ele quer na verdade que você o ajude a descobrir de quantas formas é possível ganhar esse jogo.

Entrada

 

A entrada possui duas linhas. A primeira linha contém apenas um inteiro N que indica o número de quadrados na fileira de um jogo. A segunda linha contém N inteiros indicando na ordem os números presentes nos quadrados da fileira de um jogo.

 

Saída

Seu programa deve imprimir uma única linha, contendo apenas um inteiro, o número de maneiras de ganhar o jogo apresentado na entrada. Se não for possível que o jogador ganhe o jogo, imprima 0.

Restrições

  • 1 ≤ N ≤ 1000000
  • Os números nos quadrados são inteiros não negativos menores ou iguais a 1000.

Exemplos

Entrada
6
3 4 6 0 2 9

Saída
3

Entrada
7
1 1 1 1 1 1 1

Saída
0

Entrada
5
8 0 8 0 8

Saída
15

Adicionado por:Marcos Kawakami
Data:2014-02-24
Tempo limite:1s-3s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:OBI 2013 - Fase 2 Nível 1

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.