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$ 種建構樹並比較子節點的方法：