{"problem":{"name":"Sum of Minimum Distance","description":{"content":"You are given positive integers $A$, $B$, $X$, $Y$, and $N$. Here, the following is guaranteed: *   $A<B$ *   $\\gcd(A,B)=1$ *   $1 \\leq N \\leq A+B-1$ For an integer $n$, define $f(n)$ as follows: *","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc183_f"},"statements":[{"statement_type":"Markdown","content":"You are given positive integers $A$, $B$, $X$, $Y$, and $N$. Here, the following is guaranteed:\n\n*   $A<B$\n*   $\\gcd(A,B)=1$\n*   $1 \\leq N \\leq A+B-1$\n\nFor an integer $n$, define $f(n)$ as follows:\n\n*   You start with an integer $x=0$. $f(n)$ is the minimum total cost to achieve $x=n$ by repeatedly performing the following operations.\n    *   Replace the value of $x$ with $x+A$. The cost of this operation is $X$.\n    *   Replace the value of $x$ with $x-A$. The cost of this operation is $X$.\n    *   Replace the value of $x$ with $x+B$. The cost of this operation is $Y$.\n    *   Replace the value of $x$ with $x-B$. The cost of this operation is $Y$.\n\nIt can be proved from the constraints on $A$ and $B$ that $f(n)$ is defined for any integer $n$.\nFind the value of $\\sum_{1 \\leq n \\leq N} f(n)$, modulo $998244353$.\nThere are $T$ test cases for each input.\n\n## Constraints\n\n*   $1 \\leq T \\leq 1000$\n*   $1 \\leq A<B \\leq 10^9$\n*   $\\gcd(A,B)=1$\n*   $1 \\leq X,Y \\leq 10^9$\n*   $1 \\leq N \\leq A+B-1$\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$T$\n$case_1$\n$case_2$\n$\\vdots$\n$case_T$\n\nEach test case is given in the following format:\n\n$A$ $B$ $X$ $Y$ $N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc183_f","tags":[],"sample_group":[["4\n1 2 1 1 2\n3 5 2 4 6\n79 85 72 95 4\n80980429 110892168 22712439 520643153 66132787","2\n34\n18111\n785776602\n\nIn the first test case, $f(1)=1$ and $f(2)=1$.\nIn the second test case, $f(1)=8$, $f(2)=6$, $f(3)=2$, $f(4)=10$, $f(5)=4$, and $f(6)=4$."]],"created_at":"2026-03-03 11:01:14"}}