{"problem":{"name":"Block Game","description":{"content":"There is a sequence of cells that extends infinitely to both directions. You and Snuke play the following game: *   The judge chooses a string $t$ consisting of `B` and `S`, called turn string, and s","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc050_c"},"statements":[{"statement_type":"Markdown","content":"There is a sequence of cells that extends infinitely to both directions. You and Snuke play the following game:\n\n*   The judge chooses a string $t$ consisting of `B` and `S`, called turn string, and show it to both players.\n*   First, Snuke stands on one of the cells.\n*   Then, for each $i = 1, ..., |t|$ in this order, the following happens:\n    *   If the $i$\\-th letter of $t$ is `B`, it is your turn. You choose a cell that contains neither other blocks nor Snuke, and put a block on the cell. After that, if both of the two cells adjacent to Snuke's cell are blocked, you win and the game ends.\n    *   If the $i$\\-th letter of $t$ is `S`, it is Snuke's turn. He may move to an adjacent unblocked cell, or doesn't do anything.\n*   If the game still hasn't ended, Snuke wins and the game ends.\n\nYou are given a string $s$ consisting of `B`, `S`, and `?`. If $s$ contains $Q$ `?`s, there are $2^Q$ ways to replace each `?` with `B` or `S` and get a turn string. Among those $2^Q$ strings, how many will end up with your winning, in case both players play optimally? Find the answer modulo $998,244,353$.\n\n## Constraints\n\n*   $1 \\leq |s| \\leq 10^6$\n*   $s$ consists of `B`, `S`, and `?`.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$s$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc050_c","tags":[],"sample_group":[["BSSBS","0\n\nYou take the $1$st and the $4$th turn, and Snuke takes the $2$nd, the $3$rd, and the $5$th turn. In this case, if both players play optimally, it turns out that Snuke wins."],["?S?B????S????????B??????B??S??","16777197"]],"created_at":"2026-03-03 11:01:14"}}