Monety

Limit pamięci: 16 MB

Bajtazar jest niezwykle dumny ze swojej kolekcji rzadkich monet. Zbierał je przez wiele lat, dbając o to, by żadne dwie nie były do siebie podobne. Obecnie ma monet ponumerowanych tak, że -ta moneta ma rozmiar dokładnie .

Jako że kolekcja Bajtazara ostatnio się powiększyła, był on zmuszony kupić nowy klaser. Jest w nim dokładnie przegród na monety, każda o określonym rozmiarze. Oczywiście żadnej monety nie można włożyć do zbyt małej przegrody. Nic nie stoi jednak na przeszkodzie, by włożyć ją do przegrody większej.

Bajtazar zastanawia się teraz do których przegród włożyć poszczególne monety. Po sprawdzeniu wielu kombinacji zaintrygowało go również pytanie, na ile sposobów może zapełnić klaser. Ponieważ liczba ta może być bardzo duża, Bajtazarowi wystarczy jej reszta z dzielenia przez . Napisz program, który zaspokoi jego ciekawość.

Wejście

Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą: (). W następnym wierszu znajduje się liczb całkowitych () pooddzielanych pojedynczymi odstępami. Liczba mówi, jaką największą monetę można włożyć do -tej przegrody.

Możesz założyć, że w testach wartych co najmniej punktów zachodzi dodatkowo warunek: .

Wyjście

Twój program powinien wypisać na standardowe wyjście jedną liczbę całkowitą - resztę z dzielenia liczby sposobów zapełnienia klasera przez .

Przykład

Dla danych wejściowych:

4
4 2 4 2

poprawną odpowiedzią jest:

4

Autor zadania: Michał Włodarczyk.