AT_abc446_e [ABC446E] Multiple-Free Sequences

Among integer pairs $ (x, y) $ satisfying $ 0 \leq x,y \leq M-1 $ , how many are there such that the infinite sequence $ (s_1, s_2, \dots) $ defined by the following recurrence relation contains no multiples of $ M $ ? - $ s_1 = x $ - $ s_2 = y $ - $ s_n = A s_{n-1} + B s_{n-2} $ ( $ n \geq 3 $ )

The input is given from Standard Input in the following format: > $ M $ $ A $ $ B $

Output the answer on one line.

### Sample Explanation 1 The integer pairs satisfying the condition in the problem statement are $ (x,y) = (1,1), (1,3), (2,1), (2,2), (2,3), (3,1), (3,3) $ , for a total of seven pairs. For example, when $ (x,y) = (2,1) $ , the corresponding sequence is $ (2,1,5,7,17,31,65,127,\dots) $ . This sequence contains no multiples of $ 4 $ . Thus, $ (x,y) = (2,1) $ satisfies the condition in the problem statement. On the other hand, when $ (x,y) = (3,2) $ , the corresponding sequence is $ (3,2,8,12,28,52,108,212,\dots) $ . The third term of this sequence is $ 8 $ , which is a multiple of $ 4 $ . Thus, $ (x,y) = (3,2) $ does not satisfy the condition in the problem statement. ### Sample Explanation 2 No integer pairs satisfy the condition in the problem statement. ### Constraints - $ 2 \leq M \leq 1000 $ - $ 0 \leq A, B \leq M-1 $ - All input values are integers.