Bessie ottiene un numero pari#11167

Bessie ottiene un numero pari

1 secondo

128 megabyte

Media

Fattore John e la mucca Bessie amano scambiarsi rompicapi matematici nel tempo libero. L'ultimo rompicapo che FJ ha dato a Bessie si è rivelato piuttosto complicato, e lei non è riuscita a risolverlo. Ora vuole vendicarsi con FJ, proponendogli un rompicapo altrettanto difficile.

Bessie propone a FJ la seguente espressione

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

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

che contiene sette variabili $B, E, S, I, G, O$ B, E, S, I, G, O e $M$ .

(Si noti che $O$ è una variabile, non la cifra $0$ .)

Per ciascuna variabile, Bessie fornisce a FJ un elenco contenente non più di $20$ valori interi che quella variabile può assumere. Lei chiede a FJ di contare il numero di modi distinti per assegnare valori alle variabili in modo che l'intera espressione risulti in un valore pari.

Input

La prima riga contiene un numero intero $n$ .

Nelle successive $n$ righe, ogni riga contiene una variabile e un possibile valore di quella variabile. Ogni variabile compare in questo elenco almeno una volta e al massimo $20$ volte. Lo stesso possibile valore non compare più di una volta per la stessa variabile.

Tutti i possibili valori sono compresi nell'intervallo da $- 300$ a $300$ .

Output

Stampa un singolo numero intero — il numero di modi per assegnare valori alle variabili in modo che l'espressione sopra abbia un valore pari.

Esempi

Esistono $6$ modi possibili per assegnare valori alle variabili:

(B,E,S,I,G,O,M) = (2, 5, 7, 10, 1, 16, 19) -> 53,244
                = (2, 5, 7, 10, 1, 16, 2)  -> 35,496
                = (2, 5, 7, 9,  1, 16, 2)  -> 34,510
                = (3, 5, 7, 10, 1, 16, 2)  -> 36,482
                = (3, 5, 7, 9,  1, 16, 19) -> 53,244
                = (3, 5, 7, 9,  1, 16, 2)  -> 35,496

Note Si noti che $(2, 5, 7, 10, 1, 16, 19)$ (2,5,7,10,1,16,19) e $(3, 5, 7, 9, 1, 16, 19)$ (3,5,7,9,1,16,19) sono considerati modi di assegnazione distinti, nonostante producano lo stesso valore dell'espressione, poiché i valori sono assegnati alle variabili in modo diverso.

Esempio 1