Archiwum zadań programistycznych WWSI

Od połowy listopada do połowy grudnia wywiad angielski - jeden z najbardziej elitarnych wywiadów na świecie, prowadził szeroko zakrojoną akcję rekrutacji przez Internet. Aby zostać zaproszonym na rozmowę kwalifikacyjną wystarczyło w określonym czasie złamać podany na stronie szyfr. Termin do kiedy można było nadsyłać rozwiązania co prawda już się skończył, lecz stoisz przed okazją wstąpienia do organizacji zdecydowanie bardziej elitarnej...

Tak! Zgadłeś! Koło Naukowe Miłośników Algorytmów rekrutuje! Co zrobić, aby do nas dołączyć? Wystarczy otrzymać AC dla tego zadania, a być może odezwiemy się właśnie do Ciebie ;-)

Skoro wiesz już jak ogromna jest stawka, pora opisać przygotowany przez nas problem. Nasz szyfr umieszczony jest na m tablicach o wymiarach 2ⁿ × 5ⁿ. W każdej komórce tablicy znajduje się jeden znak. Szyfr składa się z m znaków - każdy znak bierzemy z kolejnej tablicy (zaczynając od pierwszej i kończąc na m-tej). Twoim zadaniem jest podanie ile różnych ciągów znaków może być wynikiem zadania.

Wejście

W pierwszej linii wejścia znajduje się dokładnie jedna liczba całkowita Z (1 ≤ Z ≤ 7) określająca liczbę zestawów danych.

Pierwsza linia każdego zestawu danych zawiera jedną liczbę całkowitą m (1 ≤ m ≤ 1000) opisującej ilość tablic w danym zestawie danych. Kolejne m linii zawiera po jednej liczbie całkowitej n (1 ≤ n ≤ 10⁷). Liczby opisują wielkość kolejnych tablic.

Wyjście

Dla każdego zestawu danych należy w osobnej linii wypisać liczbę różnych ciągów jakie można otrzymać odczytując znaki z tablic (zakładamy, że każdy znak wystąpi dokładnie w jednej tablicy i że żaden znak w tablicy nie występuje więcej niż raz).

Przykład

Wejście:

1
2
3
2

Wyjście:

100000