Problem L: Product

Problem

会津君は、素数$P$、自然数からなる集合$G$、自然数$A$を使ってゲームをすることにしました。

まず、会津君は手元の紙に$1$を書きます。その後、以下の一連の操作を任意の回数行います。

• $G$から要素を一つ選ぶ。これを$g$とする。
• 手元の紙に書かれた数と$g$との積を新しく紙に書く。
• 元々紙に書かれていた数を消す。

手元の紙に書かれた数を$P$で割ったあまりと$A$が等しければ会津君の勝ちで、そうでなければ負けです。$P$、$G$、$A$が与えられたときに会津君が勝つことができるか判定してください。

Input

入力は以下の形式で与えられる。

$P$ $T$
$Test_1$
$\vdots$
$Test_{T}$

入力は複数のテストケースからなる。まず$1$行に素数$P$とテストケースの数$T$が与えられる。$P$は全てのテストケースで共通である。続く$T$行に各テストケースが与えられる。

各テストケースは以下のように与えられる。

$|G|$ $G_1$ $\dots$ $G_{|G|}$ $A$

各テストケースでは、$G$の要素数、$G$の各要素、$A$が順番に空白で区切られて与えられる。

Constraints

入力は以下の条件を満たす。

• 入力はすべては整数である。
• $2 \le P \le 2^{31}-1$
• $1 \le T,|G| \le 10^5$
• $1 \le G_i,A \le P-1$
• $G_i \ne G_j,$ if $i \ne j$
• 全てのテストケースの$|G|$の総和は$10^5$を超えない。

Output

各テストケースに対して、会津君が勝つことができるならば$1$を、そうでなければ$0$を一行に出力する。

Sample Input 1

7 3
1 1 2
1 2 1
3 1 2 4 5

Sample Output 1

0
1
0

Sample Input 2

1000000007 8
3 2 9 7 5
3 2 9 5 1000001
3 39 1002 65537 12
2 1000000006 518012930 793649232
10 459268180 313723762 835892239 612038995 90424474 366392946 38051435 854115735 5132833 320534710 421820264
1 1 1
1 1 1000000006
1 1000000006 1

Sample Output 2

0
1
1
1
0
1
0
1

Note

Link

 

---