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.

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.

Constraints

• $2\leq N\leq 10^6$
• $1\leq a,b,c,d\leq 10^6$

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.

见题面 Input 部分

见题面 Output 部分