Yana, Mino, White và Huzz là những người bạn thân nhất của nhau.

Dạo gần đây Mino cảm thấy rất bối rối. Ám ảnh bởi những thất bại trong quá khứ ở OI, cậu gặp nhiều khó khăn trong việc lên kế hoạch cho tương lai trong khi phải xoay xở với lịch học bận rộn ở trường. Ba người bạn của cậu gợi ý rằng cậu nên đánh giá mức độ quan trọng của các công việc và sắp xếp thứ tự ưu tiên cho chúng.

Giả sử có $n$ công việc khác nhau được đánh số từ $1$ đến $n$. Mỗi lần, Huzz chọn hai công việc kề nhau, White so sánh chúng, và Yana gộp chúng lại thành một công việc duy nhất. Mino ngạc nhiên nhận ra rằng quá trình này tình cờ tạo thành một cây phân đoạn (segment tree), nhưng không nhất thiết phải chia đôi ở chính giữa. Chính xác hơn, nó tạo thành một cây có $2n - 1$ nút, trong đó mỗi cây con tương ứng với một đoạn liên tiếp. Lưu ý rằng tất cả $n$ công việc đều là các nút lá, trong khi $n - 1$ nút còn lại mỗi nút có đúng hai nút con. Những nút được tạo ra từ phép so sánh này xác định giá trị của các cạnh nối tới hai nút con của chúng: $0$ cho nút con nhỏ hơn và $1$ cho nút con lớn hơn.

Mino rất thích tính toán. Cậu định nghĩa trọng số của mỗi công việc là tổng XOR của các cạnh dọc theo đường đi từ công việc đó đến nút gốc. Cậu tự hỏi: nếu biết trước các trọng số, có bao nhiêu cách để xây dựng những cây như vậy và so sánh các nút con?

Một lần nữa, Mino không giỏi OI, đó là lý do cậu tìm đến sự giúp đỡ của bạn. Để đơn giản hóa bài toán, bạn chỉ cần tìm đáp án theo modulo $998,244,353$.

Dữ liệu

Dòng đầu tiên của dữ liệu vào chứa một số nguyên dương $n$ ($1 \le n \le 250000$), số lượng công việc.

Dòng thứ hai chứa một xâu nhị phân $S$ có độ dài $n$, trong đó $S_i$ biểu thị tổng Bitwise-XOR của tất cả các giá trị trên các cạnh từ công việc $i$ đến nút gốc.

Kết quả

In ra một số nguyên là đáp án theo modulo $998,244,353$.

Ví dụ

Dữ liệu

4
0101

Kết quả

6

Giải thích

Có $6$ cách để xây dựng cây và so sánh các nút con: