Problem description


Mozaika
(mozaika)
Memory limit: 64 MB
Time limit: 10.00 s

Kilka lat temu zaczęła się budowa perły Cesarstwa – niemal doskonałej świątyni z olbrzymią kopułą. Budowa powoli dobiega już końca, jednak do pełnej doskonałości budowli brakuje tylko jednego: mozaiki na posadzce. By mozaika była dobra, musi być zbudowana z kwadratowych kamyczków tego samego rozmiaru, cała musi mieć kształt kwadratu i musi się składać z kamyczków w dokładnie dwóch kolorach.

Twoim zadaniem będzie kupienie na lokalnym targowisku materiałów na tę finalną mozaikę. W sekcji kamieniarskiej targowiska są tylko dwaj kupcy: Kwadratus i Liniusz. Kwadratus sprzedaje tylko białe kamyczki i za K talarów otrzymasz u niego K2 kamyczków. Liniusz natomiast sprzedaje droższe, pozłacane kamyczki i za K talarów możesz od niego dostać K kamyczków.

Targowisko jest już bliskie zamknięcia, kupcy chcą już zamykać stanowiska, więc każdemu z dwóch kupców możesz zapłacić tylko jedną monetą. Na ten zakup kwestor przyznał Ci N monet o nominałach A1, A2, …, AN. Nominały w Cesarstwie nie są przypadkowe – dla wygody nominały nie mają dzielników pierwszych większych od 5.

Sytuacja staje się napięta, bo kupcy już zamykają stanowiska, mozaikę trzeba wykonać jak najszybciej, a możliwych zakupów jest dużo. Ale właściwie to jak dużo? Na ile sposobów możesz wręczyć Kwadratusowi i Liniuszowi dwie monety tak, by otrzymane od nich kamyczki mogły wszystkie złożyć się na dobrą mozaikę?

Wejście

W pierwszym wierszu wejścia znajduje się jedna dodatnia liczba całkowita N, określająca liczbę Twoich monet. W drugim wierszu wejścia znajduje się N liczb całkowitych A1, A2, …, AN pooddzielanych pojedynczymi odstępami i określających nominały kolejnych monet w talarach.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna nieujemna liczba całkowita, określająca liczbę sposobów wręczenia kupcom monet tak, by z uzyskanych w ten sposób kamyczków dało się stworzyć dobrą mozaikę.

Ograniczenia

1 ≤ N ≤ 100 000, 1 ≤ Ai ≤ 1018, liczby Ai są postaci 2ni3mi5ki dla nieujemnych i całkowitych ni, mi, ki.

Przykład

Input Output Explanation
5
1 1 16 3 5
3

3 sposoby: Kwadratus dostaje monetę A1, Liniusz dostaje monetę A4 i powstaje mozaika 2 × 2; Kwadratus dostaje monetę A2, Liniusz dostaje monetę A4 i powstaje mozaika 2 × 2; Kwadratus dostaje monetę A4, Liniusz dostaje monetę A3 i powstaje mozaika 5 × 5.

Input Output Explanation
4
2 3 5 5
2

2 sposoby: Kwadratus dostaje monetę A1, Liniusz dostaje monetę A3 i powstaje mozaika 3 × 3; Kwadratus dostaje monetę A1, Liniusz dostaje monetę A4 i powstaje mozaika 3 × 3.

Input Output Explanation
5
3 3 5 3 12
0

Nie da się ułożyć dobrej mozaiki.