Yana、Mino、White 同 Huzz 係最好嘅朋友。

Mino 最近覺得好迷惘。因為沉迷於過去喺 OI 入面嘅失敗，佢喺應付繁忙嘅學校日程嘅同時，一直好難規劃自己嘅未來。佢嘅三個朋友建議佢評估各項任務嘅重要性並排定優先次序。

假設有 $n$ 個唔同嘅任務，編號由 $1$ 到 $n$。每次，Huzz 揀兩個相鄰嘅任務，White 對佢哋進行比較，而 Yana 將佢哋合併成一個任務。Mino 驚訝咁發現，呢個過程意外咁形成咗一棵線段樹，但呢棵樹唔一定喺正中間分裂。更準確嚟講，佢形成咗一棵有 $2n - 1$ 個節點嘅樹，其中每棵子樹都對應一個連續區間。注意，所有 $n$ 個任務都係葉節點，而其餘 $n - 1$ 個節點每個都有兩個子節點。呢啲由比較產生嘅節點定義咗連去佢哋子節點嘅邊權：連去較小嗰個子節點嘅邊權係 $0$，連去較大嗰個子節點嘅邊權係 $1$。

Mino 非常鍾意計算。佢將每個任務嘅權值定義為由嗰個任務去到根節點嘅路徑上面所有邊權嘅異或和（XOR sum）。佢想知道：如果俾定呢啲權值，有幾多種方法可以構造出呢種樹並對子節點進行比較？

再一次，Mino 並唔擅長 OI，所以佢搵你幫手。為咗簡化問題，你只需要求出答案對 $998,244,353$ 取模嘅結果。

輸入格式

輸入嘅第一行包含一個正整數 $n$（$1 \le n \le 250000$），代表任務嘅數量。

第二行包含一個長度為 $n$ 嘅二進制字串 $S$，其中 $S_i$ 代表由任務 $i$ 去到根節點嘅路徑上面所有邊權嘅按位元異或和。

輸出格式

輸出一個整數，即答案對 $998,244,353$ 取模嘅結果。

範例

輸入

4
0101

輸出

6

提示

有 $6$ 種方法構造呢棵樹並對子節點進行比較：