Problema L - Restaurante do João

Este problema foi proposto no âmbito de um dos guias de introdução das ONI. No texto original podem encontrar mais informação sobre o problema assim como alguns conceitos que precisam de saber para o resolver. O artigo é o seguinte: http://oni.dcc.fc.up.pt/loop/guias/inicial/mat/.

O João é dono de um dos maiores restaurantes da zona. Todos vão ao seu restaurante e por isso há sempre muita procura por pratos novos. Para sistematizar a criação de pratos, o João agrupou os vários ingredientes que tem disponível em N grupos, onde cada ingrediente encontra-se em exatamente um grupo. O i-ésimo grupo tem exatamente g_i ingredientes. Para criar um prato, o João pode escolher um ingrediente de cada grupo, mas não mais que 1.

Nota que não é preciso escolher ingredientes de todos os grupos, mas é preciso escolher pelo menos 1 ingrediente. O João quer saber o número de pratos diferentes que este sistema lhe permite criar. Como este número pode ser muito grande, o João quer saber o seu valor módulo 12345.

O Problema

Dado o número de ingredientes do João N e a quantidade g_i que ele tem de cada ingrediente calcula o número de pratos diferentes qu ele pode fazer módulo 12345.

Input

Um inteiro N numa linha, o número de ingredientes. De seguida vem uma linha com N inteiros com a quantidade de cada ingrediente.

Output

Um inteiro entre 0 e 12344 que indica o número de pratos diferentes que o João pode fazer com os ingredientes que tem módulo 12345.

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

1 ≤ N ≤ 1 000 000		Números de ingredientes
1 ≤ G_i ≤ 12345		Quantidade de cada ingrediente

Os casos de teste deste problema estão organizados em 2 grupos com restrições adicionais diferentes:

Grupo	Número de Pontos	Restrições adicionais
1	40	N ≤ 1000
2	60	-

Input do Exemplo 1

4
10 8 21 5

Output do Exemplo 1

Input do Exemplo 2

5
100 200 300 400 500