W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
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ść.
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: .
Twój program powinien wypisać na standardowe wyjście jedną liczbę całkowitą - resztę z dzielenia liczby sposobów zapełnienia klasera przez .
Dla danych wejściowych:
4 4 2 4 2
poprawną odpowiedzią jest:
4
Autor zadania: Michał Włodarczyk.