Welcome to ZOJ
 Problem Sets Information Select Problem Runs Ranklist
ZOJ Problem Set - 2612
Stable Sets

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Consider integer numbers in range from 0 to r-1 for some r. They form a ring, denoted by Zr. That means that you can perform addition, substraction and multiplication of the numbers, each time taking the result modulo r.

Let us call some subset A {0, 1, ... , r-1} stable with respect to a polynomial p(x) if A = {p(x)|x A}. Note that the empty set is always stable with respect to any polynomial.

Consider two polynomials

p(x) = anxn + an-1xn-1 + ... + a1x + a0
and
q(x) = bmxm + bm-1xm-1 + ... + b1x + b0.

Your task is to calculate the number of subsets of Zr that are stable with repsect to both p(x) and q(x).

Input

The input contains one or more test cases. In each case, the first line contains r (2 <= r <= 100). Next line describes p(x), its degree n (0 <= n <= 100) is followed by n+1 integer numbers ranging from 0 to r-1, they define an, an-1, ... , a0. Next line describes q(x) in a similar way. A constant zero polynomial has the degree of 0 for the purpose of this problem.

A case with r = 0 ends up the input file, which should not be proceeded.

Output

For each test case, output the only number - the number of subsets of Zr that are stable with repsect to both p(x) and q(x).

Sample Input

6
1 2 0
1 1 2
0


Sample Output

2


Author: Andrew Stankevich
Source: Andrew Stankevich's Contest #7
Submit    Status