Problem A
Invariant sets
We consider the set of residues modulo $m$ with the addition and multiplication operations introduced on it by this module. The resulting structure is called the residue ring modulo $m$ and is denoted by $\mathbb {Z}/m$. We call the set of residues $A \subseteq \{ 0, ..., m - 1\} $ invariant with respect to the polynomial $P$ given in the ring $\mathbb {Z}/m $ if
In particular, the empty set considered as a subset of $\{ 0, ..., m - 1\} $ is an invariant set with respect to any polynomial $P$ given in the ring $\mathbb {Z}/m$. Consider the polynomials $P$ and $Q$ over the ring $\mathbb {Z}/m$:
$Q(x) = b_0 + b_1 x + ... + b_ q x^ q$.
Your task is to find the number of sets that are invariant with respect to both polynomials $P$ and $Q$.
Input
The input file consists of the following lines:
-
The first line contains the number $m$ ($2 \leq m \leq 100$).
-
The second line contains the polynomial $P$: the degree $p$ ($0 \leq p \leq 100$) is given at the beginning, and then the coefficients $a_ p, ..., a_0$, which are integers from 0 to $m-1$, inclusive.
-
The third line contains the polynomial $Q$ in the same format. The degree of $Q$ also satisfies the constraint $0 \leq q \leq 100$.
Output
Write out on one line the found number of invariant sets.
| Sample Input 1 | Sample Output 1 |
|---|---|
6 1 2 0 1 1 2 |
2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 1 1 0 1 1 0 |
16 |
