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 long long MOD = 998244353;
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 lspread(int i, int val, vector<bool>& vstl, vector<bool>& vstr) {
    vstl[i] = true;
    if (val && lfix[i] && lfix[i] != val) {
      return false;
    }
    for (auto& e : ls[i]) {
      if (vstr[e.first]) continue;
      if (!rspread(e.first, val * e.second, vstl, vstr)) {
        return false;
      }
    }
    return true;
  }
  bool rspread(int i, int val, vector<bool>& vstl, vector<bool>& vstr) {
    vstr[i] = true;
    if (val && rfix[i] && rfix[i] != val) {
      return false;
    }
    for (auto& e : rs[i]) {
      if (vstl[e.first]) continue;
      if (!lspread(e.first, val * e.second, vstl, vstr)) {
        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 - i - 1;
    }
  }
  for (int i = 0; i < N; ++i) {
    if (i < (N + 1) / 2) {
      b[i] = i;
    } else {
      b[i] = N - i - 1;
    }
  }
  for (int i = 0; i < N; ++i) {
    int c = S[N - i - 1];
    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> vstl((len + 1) / 2, false);
  vector<bool> vstr((N + 1) / 2, false);
  for (int l = 0; l < (len + 1) / 2; ++l) {
    if (g.lfix[l] && !vstl[l]) {
      if (!g.lspread(l, g.lfix[l], vstl, vstr)) return 0;
    }
  }
  for (int r = 0; r < (N + 1) / 2; ++r) {
    if (g.rfix[r] && !vstr[r]) {
      if (!g.rspread(r, g.rfix[r], vstl, vstr)) return 0;
    }
  }
  long long res = 1;
  for (int l = 0; l < (len + 1) / 2; ++l) {
    if (!vstl[l]) {
      res = (res * 2) % MOD;
      g.lspread(l, 0, vstl, vstr);
    }
  }
  for (int r = 0; r < (N + 1) / 2; ++r) {
    if (!vstr[r]) {
      res = (res * 2) % MOD;
      g.rspread(r, 0, vstl, vstr);
    }
  }
  return res;
}
int main() {
  char S[1002];
  scanf("%s", S);
  int N = strlen(S);
  long long res = 0;
  for (int i = 1; i < N; ++i) {
    res = (res + work(N, S, i)) % MOD;
  }
  printf("%lld\n", res);
  return 0;
}