{"problem":{"name":"Paw","description":{"content":"There are $n$ squares arranged in a row. Each square has a left- or right-pointing footprint or a hole. The initial state of each square is described by a string $s$ consisting of `.`, `<`, `>`. If th","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc132_e"},"statements":[{"statement_type":"Markdown","content":"There are $n$ squares arranged in a row. Each square has a left- or right-pointing footprint or a hole. The initial state of each square is described by a string $s$ consisting of `.`, `<`, `>`. If the $i$\\-th character of $s$ is `.`, the $i$\\-th square from the left has a hole; if that character is `<`, that square has a left-pointing footprint; if that character is `>`, that square has a right-pointing footprint.\nSnuke, the cat, will repeat the following procedure until there is no more square with a hole.\n\n*   Step $1$: Choose one square with a hole randomly with equal probability.\n*   Step $2$: Fill the hole in the chosen square, stand there, and face to the left or right randomly with equal probability.\n*   Step $3$: Keep walking in the direction Snuke is facing until he steps on a square with a hole or exits the row of squares.\n\nHere, the choices of squares and directions are independent of each other.\nWhen Snuke walks on a square (without a hole), that square gets a footprint in the direction he walks in. If the square already has a footprint, it gets erased and replaced by a new one. For example, in the situation `>.<><.><`, if Snuke chooses the $6$\\-th square from the left and faces to the left, the $6$\\-th, $5$\\-th, $4$\\-th, $3$\\-rd squares get left-pointing footprints: `>.<<<<><`.\nFind the expected value of the number of left-pointing footprints when Snuke finishes the procedures, modulo $998244353$.\n\n## Constraints\n\n*   $1 \\leq n \\leq 10^5$\n*   $s$ is a string of length $n$ consisting of `.`, `<`, `>`.\n*   $s$ contains at least one `.`.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$n$\n$s$\n\n[samples]\n\n## Notes\n\nWhen the sought expected value is represented as an irreducible fraction $p/q$, there uniquely exists an integer $r$ such that $rq\\equiv p ~(\\text{mod } 998244353)$ and $0 \\leq r \\lt 998244353$ under the Constraints of this problem. This $r$ is the value to be found.","is_translate":false,"language":"English"}],"meta":{"iden":"arc132_e","tags":[],"sample_group":[["5\n><.<<","3\n\nIn Step $1$, Snuke always chooses the only square with a hole.\nIf Snuke faces to the left in Step $2$, the squares become `<<<<<`, where $5$ squares have left-pointing footprints.\nIf Snuke faces to the right in Step $2$, the squares become `><>>>`, where $1$ square has a left-pointing footprint.\nTherefore, the answer is $\\frac{5+1}{2}=3$."],["20\n>.>.<>.<<.<>.<..<>><","848117770"]],"created_at":"2026-03-03 11:01:14"}}