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.
Dane jest wyrażenie matematyczne , w którym występują: stałe od 0 do 9, zmienne od do , a także operacje: dodawania, mnożenia i potęgowania o stałym wykładniku. Co ciekawe, każda ze zmiennych występuje w wyrażeniu co najwyżej raz. Zastanawiamy się, dla danej liczby pierwszej , ile pierwiastków modulo ma wielomian wyznaczony przez to wyrażenie. Innymi słowy, pytamy, ile jest podstawień liczb od do pod zmienne występujące w , dla których wartość wyrażenia jest podzielna przez . Ponieważ szukana liczba pierwiastków może być duża, wystarczy nam reszta z jej dzielenia przez .
Przykładowo, wielomian reprezentowany przez wyrażenie
ma 15 pierwiastków modulo , m.in. następujące trzy pierwiastki:
Formalnie, wyrażenie definiujemy następująco:
Pierwszy wiersz wejścia zawiera jedną liczbę pierwszą (). Drugi wiersz zawiera wyrażenie zgodne z podaną specyfikacją, opisane przez ciąg złożony z co najwyżej 300 znaków 0, 1, ..., 9, a, b, ..., z, +, *, ^, (, ). W podanym ciągu nie występują odstępy.
Oznaczmy przez liczbę pierwiastków modulo wielomianu . Twój program powinien wypisać jedną nieujemną liczbę całkowitą: resztę z dzielenia przez .
Dla danych wejściowych:
3 (((a+y)*(z+8))^2)
poprawną odpowiedzią jest:
15
Autor zadania: Jakub Radoszewski.