Consider an expression
, containing
integer constants from 0 to 9, variables from
to
,
and the following operations: addition, multiplication and exponentiation
with a constant exponent.
Quite surprisingly, each of the variables
appears in the expression
at most once.
For a given prime number
, we would like to know how many roots modulo
the polynomial represented by this expression has.
In other words, we want to count the number of ways in which integers from
to
can be assigned to the variables in
, so that the value of
is divisible by
.
Since the number of such roots can turn out large, it suffices to output it
modulo
.
For example, the polynomial represented by the following expression:
has 15 roots modulo
, among which the roots:
can be found.
More formally, an expression is defined as follows:
The first line of input contains one prime number
(
).
The second line contains an expression
as specified above, described
by a sequence of at most 300 characters
0, 1, ..., 9, a, b, ..., z,
+, *, ^,
(, ),
without any white space.
Let
denote the number of roots modulo
of the polynomial
.
Your program should output one non-negative integer,
.
For the input data:
3 (((a+y)*(z+8))^2)
the correct result is:
15
Task author: Jakub Radoszewski.
W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem szkopul@fri.edu.pl.
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, odwiedź nasze serwery na Discordzie. Są one moderowane przez społeczność, ale członkowie zespołu wsparcia również aktywnie się tam udzielają.