think-cell Round 1 |
---|
Finished |
You are given a binary$$$^\dagger$$$ pattern $$$p$$$ of length $$$n$$$.
A binary string $$$q$$$ of the same length $$$n$$$ is called good if for every $$$i$$$ ($$$1 \leq i \leq n$$$), there exist indices $$$l$$$ and $$$r$$$ such that:
Count the number of good binary strings modulo $$$998\,244\,353$$$.
$$$^\dagger$$$ A binary string is a string that only consists of characters $$$\mathtt{0}$$$ and $$$\mathtt{1}$$$.
$$$^\ddagger$$$ Character $$$c$$$ is a mode of string $$$t$$$ of length $$$m$$$ if the number of occurrences of $$$c$$$ in $$$t$$$ is at least $$$\lceil \frac{m}{2} \rceil$$$. For example, $$$\mathtt{0}$$$ is a mode of $$$\mathtt{010}$$$, $$$\mathtt{1}$$$ is not a mode of $$$\mathtt{010}$$$, and both $$$\mathtt{0}$$$ and $$$\mathtt{1}$$$ are modes of $$$\mathtt{011010}$$$.
The first line of input contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of the binary string $$$p$$$.
The second line of input contains a binary string $$$p$$$ of length $$$n$$$ consisting of characters 0 and 1.
Output the number of good strings modulo $$$998\,244\,353$$$.
10
1
3111
5
41011
9
6110001
36
12111010001111
2441
In the second example, the good strings are
Name |
---|