In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you are familiar with IRC chat, the support team is also reachable on PIRC network (irc.pirc.pl
) in #szkopul
channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
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.