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
上一题 下一题