504041 - 数论神题

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

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

输入

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

输出

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

样例

输入

    2 1 2 3 4

输出

    10

输入

    2 1 1 10 10

输出

    -1

输入

    9 12 34 56 78

输出

  827501367

时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题