AT_abc446_e [ABC446E] Multiple-Free Sequences

$ 0 \leq x,y \leq M-1 $ を満たす整数組 $ (x, y) $ のうち、以下の漸化式で表される無限長の数列 $ (s_1, s_2, \dots) $ が $ M $ の倍数を全く含まないようなものは何通りありますか？ - $ s_1 = x $ - $ s_2 = y $ - $ s_n = A s_{n-1} + B s_{n-2} $ ( $ n \geq 3 $ )

入力は以下の形式で標準入力から与えられる。 > $ M $ $ A $ $ B $

答えを $ 1 $ 行に出力せよ。

### Sample Explanation 1 問題文中の条件を満たす整数組は $ (x,y) = (1,1), (1,3), (2,1), (2,2), (2,3), (3,1), (3,3) $ の $ 7 $ 通りです。 たとえば $ (x,y) = (2,1) $ としたとき、対応する数列は $ (2,1,5,7,17,31,65,127,\dots) $ となります。この数列は $ 4 $ の倍数を全く含みません。よって、 $ (x,y) = (2,1) $ は問題文中の条件を満たします。 一方で $ (x,y) = (3,2) $ としたとき、対応する数列は $ (3,2,8,12,28,52,108,212,\dots) $ となります。この数列の第 $ 3 $ 項は $ 8 $ であり、これは $ 4 $ の倍数です。よって、 $ (x,y) = (3,2) $ は問題文中の条件を満たしません。 ### Sample Explanation 2 問題文中の条件を満たす整数組は存在しません。 ### Constraints - $ 2 \leq M \leq 1000 $ - $ 0 \leq A, B \leq M-1 $ - 入力される値はすべて整数