{"raw_statement":[{"iden":"problem statement","content":"You are given positive integers $N, a, b, c, d$.\nDetermine 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$."},{"iden":"constraints","content":"*   $2\\leq N\\leq 10^6$\n*   $1\\leq a,b,c,d\\leq 10^6$"},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $a$ $b$ $c$ $d$"},{"iden":"sample input 1","content":"2 1 2 3 4"},{"iden":"sample output 1","content":"10\n\n$x=10$ is the smallest non-negative integer such that $x\\equiv 1\\pmod{3}$ and $x\\equiv 3\\pmod{7}$."},{"iden":"sample input 2","content":"2 1 1 10 10"},{"iden":"sample output 2","content":"\\-1\n\nNo non-negative integer $x$ satisfies $x\\equiv 1\\pmod{10}$ and $x\\equiv 2\\pmod{20}$."},{"iden":"sample input 3","content":"100 20 30 2 3"},{"iden":"sample output 3","content":"0\n\n$x= 0$ is the smallest non-negative integer satisfying the condition."},{"iden":"sample input 4","content":"9 12 34 56 78"},{"iden":"sample output 4","content":"827501367\n\n$x=15977769171609124$ is the smallest non-negative integer satisfying the condition."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}