Il rompicapo di Bessie#11170
Accedi

Il rompicapo di Bessie

1 secondo
128 megabyte
Media

Il fattore John e la mucca Bessie amano scambiarsi indovinelli matematici nel tempo libero. L'ultimo indovinello che FJ ha dato a Bessie si è rivelato piuttosto difficile, ed ella non è riuscita a risolverlo. Ora Bessie vuole prendersi la rivincita e proporre a FJ un proprio difficile problema.

Bessie dà a FJ l'espressione

(B + E + S + S + I + E)(G + O + E + S)(M + O + O),

che contiene sette variabili B, E, S, I, G, O e (la variabile è la lettera "", non la cifra zero).

Per ciascuna variabile, Bessie fornisce a FJ un elenco contenente al più valori interi che tale variabile può assumere. Ella chiede a FJ di determinare il numero di modi distinti di assegnare valori alle variabili in modo che l'intera espressione sia un multiplo di .

Si noti che la risposta potrebbe non entrare in un intero a bit, quindi bisognerebbe usare interi a bit (ad esempio, long~long in C o C++).

Input

La prima riga contiene un intero . Ciascuna delle successive righe contiene una variabile e un possibile valore per quella variabile.

Ogni variabile compare nell'elenco almeno una volta e al più volte. Nessun possibile valore compare più di una volta per la stessa variabile. Tutti i possibili valori sono compresi tra -10^5 e 10^5.

Output

Stampare un singolo intero — il numero di modi in cui FJ può assegnare valori alle variabili in modo che l'espressione sopra riportata sia un multiplo di .

Esempi

Esistono due assegnazioni valide:

\begin{aligned} (B,E,S,I,G,O,M) &= (2,5,7,9,1,16,19) &&\rightarrow 51{,}765,\\ (B,E,S,I,G,O,M) &= (2,5,7,9,1,16,2) &&\rightarrow 34{,}510. \end{aligned}

Esempio 1

Loading
Loading