Palindrome XOR

Cho một xâu $s$ gồm các ký tự 1, 0 và ?. Ký tự đầu tiên của $s$ được đảm bảo là 1. Gọi $m$ là độ dài của $s$.

Đếm số cặp số nguyên $(a,b)$ thỏa mãn đồng thời các điều kiện sau:

• $1\le a<b<2^m$.
• Biểu diễn nhị phân của $a$ và biểu diễn nhị phân của $b$ (viết không có số 0 đứng đầu) đều là xâu đối xứng (palindrome).
• Biểu diễn nhị phân của $a\oplus b$ (XOR theo bit) có cùng độ dài với $s$, và với mọi vị trí $i$, ký tự thứ $i$ của xâu đó hoặc bằng ký tự thứ $i$ của $s$, hoặc ký tự thứ $i$ của $s$ là ?.

Lưu ý: $a\oplus b$ phải có đúng $m$ chữ số nhị phân (không có số 0 đứng đầu), nghĩa là bit cao nhất của $a\oplus b$ luôn là $1$ — phù hợp với $s_1=1$.

In ra kết quả theo modulo $998244353$.

Dữ liệu vào

Một dòng duy nhất chứa xâu $s$ ($1\le |s|\le 1000$) gồm các ký tự 1, 0 và ?. Ký tự đầu tiên của $s$ là 1.

Dữ liệu ra

In ra một số nguyên duy nhất là số cặp $(a,b)$ thỏa mãn các điều kiện trên, theo modulo $998244353$.

Ràng buộc

• $1\le |s|\le 1000$.
• $s$ chỉ gồm các ký tự 1, 0, ?.
• Ký tự đầu tiên của $s$ là 1.

Ví dụ