/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 1200 点
問題文
正整数 N, a, b, c, d が与えられます．
k=0,1,\ldots,N-1 すべてに対して x\equiv a+kb \pmod{c+kd} が成り立つような非負整数 x が存在するか否かを判定してください．存在する場合には，そのような x のうち最小のものを 998244353 で割った余りを求めてください．
制約
- 2\leq N\leq 10^6
- 1\leq a,b,c,d\leq 10^6
入力
入力は以下の形式で標準入力から与えられます．
N a b c d
出力
条件を満たす非負整数 x が存在しない場合には -1 を出力してください．存在する場合には，そのような x のうち最小のものを 998244353 で割った余りを出力してください．
入力例 1
2 1 2 3 4
出力例 1
10
x\equiv 1\pmod{3} かつ x\equiv 3\pmod{7} を満たす最小の非負整数は x=10 です．
入力例 2
2 1 1 10 10
出力例 2
-1
x\equiv 1\pmod{10} かつ x\equiv 2\pmod{20} を満たす非負整数は存在しません．
入力例 3
100 20 30 2 3
出力例 3
0
条件を満たす最小の非負整数は x= 0 です．
入力例 4
9 12 34 56 78
出力例 4
827501367
条件を満たす最小の非負整数は x= 15977769171609124 です．
Score : 1200 points
Problem Statement
You are given positive integers N, a, b, c, d.
Determine whether there is a non-negative integer x such that x\equiv a+kb \pmod{c+kd} for every k=0,1,\ldots,N-1. If it exists, find the smallest such x modulo 998244353.
Constraints
- 2\leq N\leq 10^6
- 1\leq a,b,c,d\leq 10^6
Input
The input is given from Standard Input in the following format:
N a b c d
Output
If there is no non-negative integer x satisfying the condition, print -1.
Otherwise, print the smallest such x modulo 998244353.
Sample Input 1
2 1 2 3 4
Sample Output 1
10
x=10 is the smallest non-negative integer such that x\equiv 1\pmod{3} and x\equiv 3\pmod{7}.
Sample Input 2
2 1 1 10 10
Sample Output 2
-1
No non-negative integer x satisfies x\equiv 1\pmod{10} and x\equiv 2\pmod{20}.
Sample Input 3
100 20 30 2 3
Sample Output 3
0
x= 0 is the smallest non-negative integer satisfying the condition.
Sample Input 4
9 12 34 56 78
Sample Output 4
827501367
x=15977769171609124 is the smallest non-negative integer satisfying the condition.