Contest Duration: - (local time) (180 minutes) Back to Home
D - Many CRT /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

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


### 入力例 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


### 入力例 4

9 12 34 56 78


### 出力例 4

827501367


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.