504041 - 数论神题

【题目描述】数论神题(genius)

给定系数N,a,b,c,d (1≤N,a,b,c,d≤106),询问同余方程组x≡a+kb (mod c+kd) 的最小非负整数解x,其中0≤k<N。

Input

输入N,a,b,c,d。

Output

由于答案较大,请输出答案对998244353 取模的结果。

Examples

Input

    2 1 2 3 4

Output

    10

Input

    2 1 1 10 10

Output

    -1

Input

    9 12 34 56 78

Output

  827501367

Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题