Problem: You are given a string s consisting of characters "1", "0", and "?". The first character of s is guaranteed to be "1". Let m be the number of characters in s.

Count the number of ways we can choose a pair of integers a, b that satisfies the following: 

  * 1 ≤ a < b < 2^m 
  * When written without leading zeros, the base-2 representations of a and b are both palindromes. 
  * The base-2 representation of bitwise XOR of a and b matches the pattern s. We say that t matches s if the lengths of t and s are the same and for every i, the i-th character of t is equal to the i-th character of s, or the i-th character of s is "?". 



Compute this count modulo 998244353. 

Input

The first line contains a single string s (1 ≤ |s| ≤ 1 000). s consists only of characters "1", "0" and "?". It is guaranteed that the first character of s is a "1".

Output

Print a single integer, the count of pairs that satisfy the conditions modulo 998244353.

Examples

Input


10110


Output


3


Input


1?0???10


Output


44


Input


1?????????????????????????????????????


Output


519569202


Input


1


Output


0

Note

For the first example, the pairs in base-2 are (111, 10001), (11, 10101), (1001, 11111).

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int N = 1000, mod = 998244353;
int add(int a, int b, int p = mod) { return a + b >= p ? a + b - p : a + b; }
int sub(int a, int b, int p = mod) { return a - b < 0 ? a - b + p : a - b; }
int mul(int a, int b, int p = mod) { return (long long)a * b % p; }
void sadd(int &a, int b, int p = mod) { a = add(a, b, p); }
void ssub(int &a, int b, int p = mod) { a = sub(a, b, p); }
void smul(int &a, int b, int p = mod) { a = mul(a, b, p); }
char s[N + 9];
int n;
void into() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
}
int a[N + 9];
void Get_a() {
  for (int i = 1; i <= n; ++i) a[i] = s[i] == '?' ? 2 : s[i] - '0';
  reverse(a + 1, a + n + 1);
}
int pw[N * 2 + 9];
void Get_pw() {
  pw[0] = 1;
  for (int i = 1; i <= n << 1; ++i) pw[i] = mul(pw[i - 1], 2);
}
struct side {
  int y, next, v;
} e[N * 20 + 9];
int lin[N * 2 + 9], cs;
void Ins(int x, int y, int v) {
  e[++cs].y = y;
  e[cs].v = v;
  e[cs].next = lin[x];
  lin[x] = cs;
}
void Ins2(int x, int y, int v) {
  Ins(x, y, v);
  Ins(y, x, v);
}
void Get_graph(int m) {
  cs = 0;
  for (int i = 1; i <= n << 1; ++i) lin[i] = 0;
  for (int i = 1; i <= n >> 1; ++i) Ins2(i, n - i + 1, 0);
  for (int i = 1; i <= m >> 1; ++i) Ins2(i + n, m - i + 1 + n, 0);
  for (int i = m + 1; i < n; ++i) Ins2(i + n, i + 1 + n, 0);
  Ins2(m + n, m + 1 + n, 1);
  for (int i = 1; i <= n; ++i)
    if (a[i] < 2) Ins2(i, i + n, a[i]);
}
int col[N * 2 + 9];
vector<int> d;
bool Dfs_col(int k, int c) {
  int res = 1;
  d.push_back(k);
  col[k] = c;
  for (int i = lin[k]; i; i = e[i].next) {
    int y = e[i].y;
    if (col[y] == -1)
      res &= Dfs_col(y, c ^ e[i].v);
    else
      res &= (c ^ e[i].v) == col[y];
  }
  return res;
}
int ans;
void Get_ans() {
  for (int i = 1; i < n; ++i) {
    Get_graph(i);
    for (int j = 1; j <= n << 1; ++j) col[j] = -1;
    int c = 0;
    for (int j = 1; j <= n << 1; ++j) {
      if (col[j] ^ -1) continue;
      d.clear();
      if (!Dfs_col(j, 0)) {
        c = -1;
        break;
      }
      int flag = 1;
      for (int vs = d.size(), j = 0; j < vs; ++j) flag &= d[j] < i + n;
      c += flag;
    }
    if (c == -1) continue;
    sadd(ans, pw[c]);
  }
}
void work() {
  Get_a();
  Get_pw();
  Get_ans();
}
void outo() { printf("%d\n", ans); }
int main() {
  int T = 1;
  for (; T--;) {
    into();
    work();
    outo();
  }
  return 0;
}