{"problem":{"name":"Ex - Inv(0,1)ving Insert(1,0)n","description":{"content":"We have a sequence $A$ consisting of integer pairs. Initially, $A = ( (0, 1), (1, 0) )$. You may perform the following operation on $A$ as many (possibly zero) times as you want: *   choose **adjacen","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":6000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc273_h"},"statements":[{"statement_type":"Markdown","content":"We have a sequence $A$ consisting of integer pairs. Initially, $A = ( (0, 1), (1, 0) )$.\nYou may perform the following operation on $A$ as many (possibly zero) times as you want:\n\n*   choose **adjacent** two integer pairs $(a, b)$ and $(c, d)$, and insert $(a + c, b + d)$ between them.\n\nFor a sequence $T$ consisting of integer pairs, let us define $f(T)$ as follows:\n\n*   let $f(T) =$ (the minimum number of operations required to make every element of $T$ contained in $A$).\n    *   We say that \"every element of $T$ is contained in $A$\" if, for all elements $x$ contained in $T$, $x$ is contained in (the set consisting of the elements contained in $A$).\n*   Here, if there are no such operations, let $f(T) = 0$.\n\nThere is a sequence $S = ((a_1, b_1), (a_2, b_2), \\dots, (a_N, b_N))$ consisting of $N$ integer pairs. Here, all elements of $S$ are pairwise distinct.  \nThere are $\\frac{N \\times (N+1)}{2}$ possible consecutive subarrays $S_{l,r}=((a_l,b_l),(a_{l+1},b_{l+1}),\\dots,(a_r,b_r))$ of $S$. Find the sum, modulo $998244353$, of $f(S_{l,r})$ over those subarrays.  \nFormally, find $\\displaystyle \\sum^{N} _ {l=1} \\sum^{N} _ {r=l} f(S_{l,r})$, modulo $998244353$.\n\n## Constraints\n\n*   $1 \\le N \\le 10^5$\n*   $0 \\le a_i,b_i \\le 10^9$\n*   $a_i \\neq a_j$ or $b_i \\neq b_j$, if $i \\neq j$.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$a_1$ $b_1$\n$a_2$ $b_2$\n$\\dots$\n$a_N$ $b_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc273_h","tags":[],"sample_group":[["7\n1 2\n3 7\n3 5\n0 0\n1000000000 1\n0 1\n6 3","3511324\n\n*   $f(S_{1,1})=2$.\n    *   We can make $((0,1),(1,0)) \\rightarrow ((0,1),(1,1),(1,0)) \\rightarrow ((0,1),(1,2),(1,1),(1,0))$.\n*   $f(S_{1,2})=5$.\n*   $f(S_{1,3})=7$.\n*   $f(S_{2,2})=5$.\n*   $f(S_{2,3})=7$.\n*   $f(S_{3,3})=4$.\n*   $f(S_{5,5})=1000000000 = 10^9$.\n*   $f(S_{5,6})=1000000000 = 10^9$.\n*   $f(S_{6,6})=0$.\n    *   $(0, 1)$ is originally contained in $A$.\n*   $f(S_{l,r})=0$ for all $S_{l,r}$ not mentioned above.\n    *   We can prove that $A$ can never contain $(0,0)$ or $(6,3)$ regardless of operations.\n\nTherefore, the sum of $f(S_{l,r})$ is $2000000030 = 2 \\times 10^9 + 30$, whose remainder when divided by $998244353$ is $3511324$."]],"created_at":"2026-03-03 11:01:14"}}