AT_agc063_d [AGC063D] Many CRT

[problemUrl]: https://atcoder.jp/contests/agc063/tasks/agc063_d 正整数 $ N,\ a,\ b,\ c,\ d $ が与えられます． $ k=0,1,\ldots,N-1 $ すべてに対して $ x\equiv\ a+kb\ \pmod{c+kd} $ が成り立つような非負整数 $ x $ が存在するか否かを判定してください．存在する場合には，そのような $ x $ のうち最小のものを $ 998244353 $ で割った余りを求めてください．

入力は以下の形式で標準入力から与えられます． > $ N $ $ a $ $ b $ $ c $ $ d $

条件を満たす非負整数 $ x $ が存在しない場合には `-1` を出力してください．存在する場合には，そのような $ x $ のうち最小のものを $ 998244353 $ で割った余りを出力してください．

### 制約 - $ 2\leq\ N\leq\ 10^6 $ - $ 1\leq\ a,b,c,d\leq\ 10^6 $ ### Sample Explanation 1 $ x\equiv\ 1\pmod{3} $ かつ $ x\equiv\ 3\pmod{7} $ を満たす最小の非負整数は $ x=10 $ です． ### Sample Explanation 2 $ x\equiv\ 1\pmod{10} $ かつ $ x\equiv\ 2\pmod{20} $ を満たす非負整数は存在しません． ### Sample Explanation 3 条件を満たす最小の非負整数は $ x=\ 0 $ です． ### Sample Explanation 4 条件を満たす最小の非負整数は $ x=\ 15977769171609124 $ です．