{"problem":{"name":"Sequence in mod P","description":{"content":"There is a sequence $X=(X_0, X_1, \\ldots)$ defined by the following recurrence relation. $X_i = \\left{ \\begin{array}{ll} S & (i = 0)\\\\ (A X_{i-1}+B) \\bmod P & (i \\geq 1) \\end{array} \\right.$ Determine","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc270_g"},"statements":[{"statement_type":"Markdown","content":"There is a sequence $X=(X_0, X_1, \\ldots)$ defined by the following recurrence relation.\n$X_i = \\left{ \\begin{array}{ll} S & (i = 0)\\\\ (A X_{i-1}+B) \\bmod P & (i \\geq 1) \\end{array} \\right.$\nDetermine whether there is an $i$ such that $X_i=G$. If it exists, find the smallest such $i$.  \nHere, $x \\bmod y$ denotes the remainder when $x$ is divided by $y$ (the least non-negative residue).\nYou are given $T$ test cases for each input file.\n\n## Constraints\n\n*   $1 \\leq T \\leq 100$\n*   $2 \\leq P \\leq 10^9$\n*   $P$ is a prime.\n*   $0\\leq A,B,S,G < P$\n*   All values in the input are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$T$\n$\\mathrm{case}_1$\n$\\mathrm{case}_2$\n$\\vdots$\n$\\mathrm{case}_T$\n\nEach test case is in the following format:\n\n$P$ $A$ $B$ $S$ $G$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc270_g","tags":[],"sample_group":[["3\n5 2 1 1 0\n5 2 2 3 0\n11 1 1 0 10","3\n-1\n10\n\nFor the first test case, we have $X=(1,3,2,0,\\ldots)$, so the smallest $i$ such that $X_i=0$ is $3$.  \nFor the second test case, we have $X=(3,3,3,3,\\ldots)$, so there is no $i$ such that $X_i=0$."]],"created_at":"2026-03-03 11:01:13"}}