Segnali di fumo

Alice e Bob sono dei turisti stranieri che hanno organizzato un’escursione sulla cima dell’Etna, dove non c’è copertura per usare i cellulari.
Dovendo comunicare da un punto all’altro dell’Etna, decidono di scambiarsi i messaggi attraverso dei segnali di fumo, vista la facile reperibilità di sbuffi fumosi sull’Etna.

Viene concordato un codice comune che utilizza due soli tipi di nuvole di fumo, piccole e grandi, facilmente distinguibili.
Viene assegnato il simbolo 0 a ciascuna nuvola piccola e il simbolo 1 a ciascuna nuvola grande.
In tal modo, i segnali di fumo sono facilmente identificabili con le sequenze binarie, composte da 0 e 1, di lunghezza arbitraria.

La lingua madre di Alice e Bob usa un alfabeto di sette lettere: A, B, C, D, E, F, G.
Viene quindi deciso di assegnare un codice binario a ciascuna delle lettere suddette:

A = 0, B = 00, C = 001, D = 010, E = 0010, F = 0100, G = 0110.

Sfortunatamente, dopo le prime trasmissioni, Alice e Bob realizzano che messaggi diversi sono codificati dalla stessa sequenza binaria.
Per esempio, quando arriva la sequenza 00100, questa è ambigua in quanto può essere stata prodotta da ADA, AF, CAA, CB oppure EA.
Con sequenze binarie più lunghe, il grado di ambiguità aumenta ulteriormente.
Inoltre, non tutte le sequenze binarie corrispondono a messaggi: per esempio, 00101 non codifica alcun messaggio, mentre 001010corrisponde a CD.

Data una sequenza binaria S, aiuta Alice e Bob a individuare l’ultima cifra x del numero (rappresentato in decimale) di messaggi diversi che hanno codifica S.
Per esempio, la sequenza S = 000000 corrisponde a 13 messaggi distinti, per cui x = 3.

Dati in Input

Il file input.txt contiene due righe.

• La prima riga contiene un intero N che rappresenta la lunghezza della sequenza binaria.
• La seconda riga contiene una sequenza binaria di N valori (0 oppure 1) separati da uno spazio.
  L’i-esimo valore in tale riga rappresenta l’i-esimo elemento della sequenza binaria.

Dati in Output

…

Assunzioni

• 1 < N < 100000
• A = 0, B = 00, C = 001, D = 010, E = 0010, F = 0100, G = 0110.

Esempi