{"problem":{"name":"Many CRT","description":{"content":"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 smalles","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc063_d"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   $2\\leq N\\leq 10^6$\n*   $1\\leq a,b,c,d\\leq 10^6$\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $a$ $b$ $c$ $d$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc063_d","tags":[],"sample_group":[["2 1 2 3 4","10\n\n$x=10$ is the smallest non-negative integer such that $x\\equiv 1\\pmod{3}$ and $x\\equiv 3\\pmod{7}$."],["2 1 1 10 10","\\-1\n\nNo non-negative integer $x$ satisfies $x\\equiv 1\\pmod{10}$ and $x\\equiv 2\\pmod{20}$."],["100 20 30 2 3","0\n\n$x= 0$ is the smallest non-negative integer satisfying the condition."],["9 12 34 56 78","827501367\n\n$x=15977769171609124$ is the smallest non-negative integer satisfying the condition."]],"created_at":"2026-03-03 11:01:14"}}