Yana、Mino、White、Huzz は親友です。

Mino は最近戸惑いを感じています。過去の OI での失敗にとらわれ、忙しい学校のスケジュールをこなしながら将来を計画するのに苦労していました。三人の友人は、タスクの重要度を評価して優先順位をつけることを提案しました。

$1$ から $n$ までの番号がついた $n$ 個の異なるタスクがあるとします。毎回、Huzz が隣接する二つのタスクを選び、White がそれらを比較し、Yana がそれらを一つのタスクに統合します。Mino は、この過程が偶然にも（必ずしも中央で分割されるとは限らない）セグメント木を形成することに気づいて驚きました。より正確には、すべての部分木が連続する区間に対応する $2n - 1$ 頂点の木を形成します。$n$ 個のタスクはすべて葉であり、残りの $n - 1$ 個の頂点はそれぞれ二つの子を持つことに注意してください。比較によって生じるこれらの頂点は、子への辺の値を定義します。小さい方の子への辺は $0$、大きい方の子への辺は $1$ です。

Mino は計算が大好きです。彼は各タスクの重みを、そのタスクから根までのパス上の辺の値の XOR 和として定義しました。彼は疑問に思います：各タスクの重みが与えられたとき、このような木を構築して子を比較する方法は何通りあるでしょうか？

やはり Mino は OI が得意ではないため、あなたに助けを求めました。問題を簡単にするため、答えを $998,244,353$ で割った余りのみを求めてください。

入力

入力の最初の行には、タスクの個数を表す正の整数 $n$（$1 \le n \le 250000$）が与えられます。

二行目には長さ $n$ の 2 進文字列 $S$ が与えられます。ここで $S_i$ はタスク $i$ から根までの辺上のすべての値のビットごとの排他的論理和（Bitwise-XOR）を表します。

出力

答えを $998,244,353$ で割った余りを表す整数を出力してください。

入出力例

入力

4
0101

出力

6

注記

木を構築して子を比較する方法は $6$ 通りあります：