{"problem":{"name":"Spoon Taking Problem","description":{"content":"$N$ people are sitting around a round table, and numbered $1$ to $N$ in a counterclockwise order. Each person has a dominant hand: left or right. There are $N$ spoons numbered $1$ to $N$ on the round ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc175_a"},"statements":[{"statement_type":"Markdown","content":"$N$ people are sitting around a round table, and numbered $1$ to $N$ in a counterclockwise order. Each person has a dominant hand: left or right.\nThere are $N$ spoons numbered $1$ to $N$ on the round table, with one spoon placed between each pair of adjacent people. For each $1 \\leq i \\leq N$, to the left and right of person $i$, there are spoons $i$ and $(i+1)$, respectively. Here, spoon $(N+1)$ refers to spoon $1$.\nBelow is a diagram for $N = 4$.\n![image](https://img.atcoder.jp/arc175/b86aef99039c82389bf15f8df725a4c5.png)\nYou are given a permutation $(P_1, \\dots, P_N)$ of $(1, \\dots, N)$. In the order $i=1,\\dots,N$, person $P_i$ will act as follows:\n\n*   If there is a spoon remaining on left or right side, they will take one of them.\n    *   If there are spoons remaining on both sides, they will take the spoon on the side of their dominant hand.\n*   Otherwise, they do nothing.\n\nYou are also given a string $S$ of length $N$ consisting of `L`, `R`, and `?`. Among the $2^N$ possible combinations of dominant hands, find how many satisfy all of the following conditions, modulo $998244353$:\n\n*   If the $i$\\-th character of $S$ is `L`, person $i$ is left-handed.\n*   If the $i$\\-th character of $S$ is `R`, person $i$ is right-handed.\n*   When everyone has finished acting, everyone has taken a spoon.\n\n## Constraints\n\n*   All input values are integers.\n*   $2 \\leq N \\leq 2 \\times 10^5$\n*   $(P_1, \\dots, P_N)$ is a permutation of $(1, \\dots, N)$.\n*   $S$ is a string of length $N$ consisting of `L`, `R`, and `?`.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$P_1$ $\\dots$ $P_N$\n$S$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc175_a","tags":[],"sample_group":[["3\n1 2 3\nL??","2\n\nWhen persons $1$, $2$, and $3$ are left-handed, left-handed, and right-handed, respectively, the actions are performed as follows:\n\n*   Person $1$ starts acting. There are spoons on both sides, so person $1$ takes spoon $1$ on the left side, which is the same as their dominant hand.\n*   Person $2$ starts acting. There are spoons on both sides, so person $2$ takes spoon $2$ on the left side, which is the same as their dominant hand.\n*   Person $3$ starts acting. There is no spoon on the right side, but spoon $3$ is remaining on the left side, so they take spoon $3$. Everyone has finished acting and taken a spoon.\n\nThis combination of dominant hands satisfies the conditions. Besides, the conditions are also satisfied when persons $1, 2, 3$ are all left-handed."],["3\n1 3 2\nR?L","0\n\nNo combinations of dominant hands satisfy the conditions."],["12\n6 2 9 3 1 4 11 5 12 10 7 8\n????????????","160"]],"created_at":"2026-03-03 11:01:14"}}