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;
int read() {
  int f = 1;
  int res = 0;
  char ch;
  do {
    ch = getchar();
    if (ch == '-') f = -f;
  } while (ch < '0' || ch > '9');
  do {
    res = res * 10 + ch - '0';
    ch = getchar();
  } while (ch >= '0' && ch <= '9');
  return f == 1 ? res : -res;
}
void fast_io() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}
const int N = 2010;
const int mod = 998244353;
const long long INF = 1e18;
int n, m, q;
int A[N], B[N], C[N];
char str[N];
int part[N];
int head[N], to[N * 4], nxt[N * 4], type[N * 4], tot;
void addEdge(int u, int v, int c) {
  tot++;
  nxt[tot] = head[u];
  to[tot] = v;
  head[u] = tot;
  type[tot] = c;
}
long long mmax(long long a, long long b) { return a > b ? a : b; }
long long mmin(long long a, long long b) { return a < b ? a : b; }
int countOne(int set) {
  int res = 0;
  while (set) {
    res++;
    set &= set - 1;
  }
  return res;
}
bool contain(int set, int i) { return (set & (1 << i)) > 0; }
long long myPow(long long a, int p) {
  if (p == 0) return 1;
  long long res = myPow(a, p / 2);
  res *= res;
  res %= mod;
  if (p % 2 == 1) {
    res *= a;
    res %= mod;
  }
  return res;
}
void addMode(int &a, long long b) { a = (a + b) % mod; }
void mySwap(int &a, int &b) {
  int tmp = a;
  a = b;
  b = tmp;
}
void mySwap(char &a, char &b) {
  char tmp = a;
  a = b;
  b = tmp;
}
bool check(int x, int p) {
  part[x] = p;
  for (int i = head[x]; i; i = nxt[i]) {
    int y = to[i];
    int c = type[i];
    if (part[y] == -1) {
      if (c == 1) {
        if (!check(y, 1 - p)) return false;
      } else {
        if (!check(y, p)) return false;
      }
    } else {
      if (c == 1 && part[y] == p) return false;
      if (c == 0 && part[y] != p) return false;
    }
  }
  return true;
}
void dfs(int x) {
  part[x] = 1;
  for (int i = head[x]; i; i = nxt[i]) {
    int y = to[i];
    if (!part[y]) {
      dfs(y);
    }
  }
}
int main() {
  fast_io();
  cin >> str;
  n = strlen(str);
  for (int i = 0; i * 2 < n; i++) {
    mySwap(str[i], str[n - i - 1]);
  }
  int res = 0;
  for (int len = 1; len < n; len++) {
    tot = 1;
    memset(head, 0, sizeof(head));
    memset(part, -1, sizeof(part));
    for (int i = 0; i < n; i++) {
      if (i == 0) {
        addEdge(i, n + len, 0);
        addEdge(n + len, i, 0);
        addEdge(i + n, n + len, 0);
        addEdge(n + len, i + n, 0);
      }
      if (i < len) {
        if (str[i] == '0') {
          addEdge(i, i + n, 0);
          addEdge(i + n, i, 0);
        } else if (str[i] == '1') {
          addEdge(i, i + n, 1);
          addEdge(i + n, i, 1);
        }
        if (i < len / 2) {
          addEdge(n + i, n + len - i - 1, 0);
          addEdge(n + len - i - 1, n + i, 0);
        }
      } else {
        if (str[i] == '0') {
          addEdge(i, n + len, 1);
          addEdge(n + len, i, 1);
        } else if (str[i] == '1') {
          addEdge(i, n + len, 0);
          addEdge(n + len, i, 0);
        }
      }
      if (i < n / 2) {
        addEdge(i, n - i - 1, 0);
        addEdge(n - i - 1, i, 0);
      }
    }
    bool ok = true;
    part[n + len] = 1;
    for (int i = head[n + len]; i; i = nxt[i]) {
      int y = to[i];
      int c = 1 - type[i];
      if (part[y] == -1) {
        if (!check(y, c)) {
          ok = false;
          break;
        }
      } else {
        if (part[y] != c) ok = false;
      }
    }
    for (int i = 0; i < n + len; i++)
      if (part[i] == -1) {
        if (!check(i, 0)) {
          ok = false;
          break;
        }
      }
    if (!ok) continue;
    memset(part, 0, sizeof(part));
    int c = 0;
    for (int i = 0; i < n + len; i++)
      if (!part[i]) {
        dfs(i);
        c++;
      }
    addMode(res, myPow(2, c - 1));
  }
  cout << res << endl;
  return 0;
}