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$인 이진 문자열 $S$가 주어지며, 여기서 $S_i$는 작업 $i$에서 루트까지 가는 간선 위의 모든 값들의 비트별 XOR(Bitwise-XOR)을 나타냅니다.

출력

답을 $998,244,353$으로 나눈 나머지를 나타내는 정수를 출력하세요.

예제

입력

4
0101

출력

6

노트

트리를 구성하고 자식을 비교하는 방법은 $6$가지가 있습니다: