Cho một xâu $a$ độ dài $n$ , chỉ gồm các ký tự 0, 1, 2.

Tồn tại một dãy $S$ độ dài $n+1$ , gồm các giá trị true (ký hiệu là 1) và false (ký hiệu là 0).

Dãy $S$ có $n$ khe trống giữa các phần tử liền kề, ta điền xâu $a$ theo thứ tự vào các khe trống:

• $a[i] = 0$ : biểu thị phép AND (&)

• $a[i] = 1$ : biểu thị phép OR (|)

• $a[i] = 2$ : biểu thị phép XOR (^)

Quy tắc tính: tính lần lượt từ trái sang phải, không xét độ ưu tiên của toán tử.

Hãy tính: số cách xây dựng dãy $S$ sao cho kết quả tính cuối cùng là true, đáp án lấy modulo $998244353$ .

Định nghĩa các phép toán

• Phép AND: 1&1=1, 1&0=0, 0&0=0

• Phép OR: $1|1=1,\ 1|0=1,\ 0|0=0$

• Phép XOR: $1\oplus1=0,\ 1\oplus0=1,\ 0\oplus0=0$

Dữ liệu vào

Dòng đầu tiên: số nguyên $n$ (độ dài của xâu $a$ )

Dòng thứ hai: xâu $a$ độ dài $n$

Dữ liệu ra

In ra số phương án sau khi lấy modulo $998244353$ .

Ví dụ

Input

7
0121111

Output

248

Ghi chú

Giới hạn dữ liệu

$1 \le n \le 10^5$