311078: CF1930I. Counting Is Fun

I. Counting Is Funtime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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:

• $1 \leq l \leq i \leq r \leq n$, and
• $p_i$ is a mode$^\ddagger$ of the string $q_lq_{l+1}\ldots q_r$.

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}$.

Input

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

Output the number of good strings modulo $998\,244\,353$.

ExamplesInput

1
0

Output

1

Input

3
111

Output

5

Input

4
1011

Output

9

Input

6
110001

Output

36

Input

12
111010001111

Output

2441

Note

In the second example, the good strings are

• $\mathtt{010}$;
• $\mathtt{011}$;
• $\mathtt{101}$;
• $\mathtt{110}$;
• $\mathtt{111}$.

题目大意：
给定一个长度为n的二进制模式p。一个长度也为n的二进制字符串q被称为“好的”，如果对于每一个i（1≤i≤n），存在索引l和r使得：
1. \(1 \leq l \leq i \leq r \leq n\)，并且
2. \(p_i\) 是字符串 \(q_lq_{l+1}...q_r\) 的众数。
计算有多少个“好的”二进制字符串，结果对 \(998,244,353\) 取模。

输入数据格式：
第一行输入一个整数n（\(1 \le n \le 10^5\)）——二进制字符串p的长度。
第二行输入一个长度为n的二进制字符串p，由字符 '0' 和 '1' 组成。

输出数据格式：
输出“好的”字符串的数量，对 \(998,244,353\) 取模的结果。题目大意： 给定一个长度为n的二进制模式p。一个长度也为n的二进制字符串q被称为“好的”，如果对于每一个i（1≤i≤n），存在索引l和r使得： 1. \(1 \leq l \leq i \leq r \leq n\)，并且 2. \(p_i\) 是字符串 \(q_lq_{l+1}...q_r\) 的众数。 计算有多少个“好的”二进制字符串，结果对 \(998,244,353\) 取模。 输入数据格式： 第一行输入一个整数n（\(1 \le n \le 10^5\)）——二进制字符串p的长度。 第二行输入一个长度为n的二进制字符串p，由字符 '0' 和 '1' 组成。 输出数据格式： 输出“好的”字符串的数量，对 \(998,244,353\) 取模的结果。