|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||128 MB||0||0||0||0.000%|
Consider an expression E, containing integer constants from 0 to 9, variables from a to z, and the following operations: addition, multiplication and exponentiation with a constant exponent. Quite surprisingly, each of the variables a, b, . . . , z appears in the expression E at most once. For a given prime number p, we would like to know how many roots modulo p the polynomial represented by this expression has. In other words, we want to count the number of ways in which integers from 0 to p − 1 can be assigned to the variables in E, so that the value of E is divisible by p. Since the number of such roots can turn out large, it suffices to output it modulo 30 011.
For example, the polynomial represented by the following expression:
E = ((a + y) · (z + 8))2
has 15 roots modulo p = 3, among which the roots:
(a = 0; y = 0; z = 0); (a = 1; y = 2; z = 0); (a = 2; y = 0; z = 1)
can be found.
More formally, an expression is defined as follows:
The first line of input contains one prime number p (2 ≤ p < 15 000). The second line contains an expression E as specified above, described by a sequence of at most 300 characters 0, 1, . . . , 9, a, b, . . . , z, +, *, ^, (, ), without any white space.
Let k denote the number of roots modulo p of the polynomial E. Your program should output one non-negative integer, k mod 30 011.