Access Counter

AtCoder

IDabc271_g

Time2000ms

Memory256MB

Difficulty—

Takahashi has decided to put a web counter on his webpage. The accesses to his webpage are described as follows: * For $i=0,1,2,\ldots,23$, there is a possible access at $i$ o'clock every day: * If $c_i=$`T`, Takahashi accesses the webpage with a probability of $X$ percent. * If $c_i=$`A`, Aoki accesses the webpage with a probability of $Y$ percent. * Whether or not Takahashi or Aoki accesses the webpage is determined independently every time. * There is no other access. Also, Takahashi believes it is preferable that the $N$\-th access since the counter is put is not made by Takahashi himself. If Takahashi puts the counter **right before $0$ o'clock** of one day, find the probability, modulo $998244353$, that the $N$\-th access is made by Aoki. ## Constraints * $1 \leq N \leq 10^{18}$ * $1 \leq X,Y \leq 99$ * $c_i$ is `T` or `A`. * $N$, $X$, and $Y$ are integers. ## Input The input is given from Standard Input in the following format: $N$ $X$ $Y$ $c_0 c_1 \ldots c_{23}$ [samples] ## Notes We can prove that the sought probability is always a finite rational number. Moreover, under the constraints of this problem, when the value is represented as $\frac{P}{Q}$ with two coprime integers $P$ and $Q$, we can prove that there is a unique integer $R$ such that $R \times Q \equiv P\pmod{998244353}$ and $0 \leq R \lt 998244353$. Find this $R$.

Samples

Input #1

1 50 50
ATATATATATATATATATATATAT

Output #1

665496236

The $1$\-st access since Takahashi puts the web counter is made by Aoki with a probability of $\frac{2}{3}$.

Input #2

271 95 1
TTTTTTTTTTTTTTTTTTTTTTTT

Output #2

0

There is no access by Aoki.

Input #3

10000000000000000 62 20
ATAATTATATTTAAAATATTATAT

Output #3

744124544

API Response (JSON)

{
  "problem": {
    "name": "Access Counter",
    "description": {
      "content": "Takahashi has decided to put a web counter on his webpage.   The accesses to his webpage are described as follows: *   For $i=0,1,2,\\ldots,23$, there is a possible access at $i$ o'clock every day:   ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc271_g"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Takahashi has decided to put a web counter on his webpage.  \nThe accesses to his webpage are described as follows:\n\n*   For $i=0,1,2,\\ldots,23$, there is a possible access at $i$ o'clock every day:\n  ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments