長さ $n$ の二項$^\dagger$パターン $p$ が与えられます。

長さ $n$ の二項文字列 $q$ が「良い」とは、すべての $i$ ($1 \leq i \leq n$) に対して、以下の条件を満たす添字 $l, r$ が存在することを指します。

• $1 \leq l \leq i \leq r \leq n$
• $p_i$ は文字列 $q_lq_{l+1}\ldots q_r$ の最頻値$^\ddagger$である。

良い二項文字列の個数を $998\,244\,353$ で割った余りを求めてください。

$^\dagger$ 二項文字列とは、文字 $\mathtt{0}$ と $\mathtt{1}$ のみからなる文字列のことです。

$^\ddagger$ 文字 $c$ が長さ $m$ の文字列 $t$ の最頻値であるとは、$t$ における $c$ の出現回数が $\lceil \frac{m}{2} \rceil$ 以上であることを指します。例えば、$\mathtt{010}$ において $\mathtt{0}$ は最頻値ですが、$\mathtt{1}$ は最頻値ではありません。また、$\mathtt{011010}$ においては $\mathtt{0}$ と $\mathtt{1}$ の両方が最頻値です。

入力

入力の1行目には、二項文字列 $p$ の長さを表す整数 $n$ ($1 \le n \le 10^5$) が与えられます。

入力の2行目には、文字 0 と 1 からなる長さ $n$ の二項文字列 $p$ が与えられます。

出力

良い文字列の個数を $998\,244\,353$ で割った余りを出力してください。

入出力例

入力 1

1
0

出力 1

1

入力 2

3
111

出力 2

5

入力 3

4
1011

出力 3

9

入力 4

6
110001

出力 4

36

入力 5

12
111010001111

出力 5

2441

注記

2番目の例において、良い文字列は以下の通りです。

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