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>
const int N = 1e6 + 10;
const int mod = 998244353;
using namespace std;
struct Bip {
  vector<vector<pair<int, int> > > ls;
  vector<vector<pair<int, int> > > rs;
  vector<int> lfix;
  vector<int> rfix;
  int L, R;
  Bip(int L_, int R_)
      : ls(L_), rs(R_), lfix(L_, 0), rfix(R_, 0), L(L_), R(R_) {}
  bool fix_l(int i, int val) {
    if (val && lfix[i] && val != lfix[i]) return false;
    lfix[i] = val;
    return true;
  }
  bool fix_r(int i, int val) {
    if (val && rfix[i] && val != rfix[i]) return false;
    rfix[i] = val;
    return true;
  }
  void add(int i, int j, int sw) {
    ls[i].emplace_back(j, sw);
    rs[j].emplace_back(i, sw);
  }
  bool ldfs(int i, int val, vector<bool> &visl, vector<bool> &visr) {
    visl[i] = true;
    if (val && lfix[i] && lfix[i] != val) return false;
    for (auto &e : ls[i]) {
      if (visr[e.first]) continue;
      if (!rdfs(e.first, val * e.second, visl, visr)) return false;
    }
    return true;
  }
  bool rdfs(int i, int val, vector<bool> &visl, vector<bool> &visr) {
    visr[i] = true;
    if (val && rfix[i] && rfix[i] != val) return false;
    for (auto &e : rs[i]) {
      if (visl[e.first]) continue;
      if (!ldfs(e.first, val * e.second, visl, visr)) return false;
    }
    return true;
  }
};
long long work(int n, const char *s, int len) {
  Bip g((len + 1) / 2, (n + 1) / 2);
  vector<int> a(len);
  vector<int> b(n);
  for (int i = 0; i < len; ++i)
    if (i < (len + 1) / 2)
      a[i] = i;
    else
      a[i] = len - 1 - i;
  for (int i = 0; i < n; ++i)
    if (i < (n + 1) / 2)
      b[i] = i;
    else
      b[i] = n - 1 - i;
  for (int i = 0; i < n; ++i) {
    int c = s[n - 1 - i];
    if (c == '?') continue;
    if (i < len)
      g.add(a[i], b[i], c == '0' ? 1 : -1);
    else if (!g.fix_r(b[i], c == '1' ? 1 : -1))
      return 0;
  }
  if (!g.fix_l(0, 1)) return 0;
  vector<bool> visl((len + 1) / 2, false);
  vector<bool> visr((n + 1) / 2, false);
  for (int l = 0; l < (len + 1) / 2; ++l) {
    if (g.lfix[l] && !visl[l]) {
      if (!g.ldfs(l, g.lfix[l], visl, visr)) return 0;
    }
  }
  for (int r = 0; r < (n + 1) / 2; ++r) {
    if (g.rfix[r] && !visr[r]) {
      if (!g.rdfs(r, g.rfix[r], visl, visr)) return 0;
    }
  }
  long long ans = 1;
  for (int l = 0; l < (len + 1) / 2; ++l) {
    if (!visl[l]) ans = ans * 2 % mod, g.ldfs(l, 0, visl, visr);
  }
  for (int r = 0; r < (n + 1) / 2; ++r) {
    if (!visr[r]) {
      ans = ans * 2 % mod;
      g.rdfs(r, 0, visl, visr);
    }
  }
  return ans;
}
int main() {
  char s[1002];
  scanf("%s", s);
  int n = strlen(s);
  int ans = 0;
  for (int i = 1; i < n; ++i) ans = (ans + work(n, s, i)) % mod;
  printf("%d\n", ans);
  return 0;
}