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 MOD = 998244353;
const int MAXN = 2010;
int Add(int a, int b, int m = MOD) {
  a += b;
  if (a >= m) a -= m;
  return a;
}
int Sub(int a, int b, int m = MOD) {
  a -= b;
  if (a < 0) a += m;
  return a;
}
int AddTo(int& to, int w, int m = MOD) {
  to += w;
  if (to >= m) to -= m;
  return to;
}
int SubTo(int& to, int w, int m = MOD) {
  to -= w;
  if (to < 0) to += m;
  return to;
}
int Mult(int a, int b, int m = MOD) { return (a * 1LL * b) % m; }
string s;
int __fixed__[MAXN];
vector<pair<int, int> > fo[MAXN];
bool used[MAXN];
vector<int> comp;
void Dfs(int vr) {
  comp.push_back(vr);
  used[vr] = true;
  for (const auto& e : fo[vr])
    if (!used[e.first]) Dfs(e.first);
}
void AddEdge(int a, int b, int v) {
  fo[a].push_back(make_pair(b, v));
  fo[b].push_back(make_pair(a, v));
}
int vals[MAXN];
bool SetVal(int vr, int to) {
  queue<int> q;
  q.push(vr);
  vals[vr] = to;
  while (!q.empty()) {
    vr = q.front();
    q.pop();
    if (__fixed__[vr] != -1 && __fixed__[vr] != vals[vr]) return false;
    for (auto& e : fo[vr]) {
      int to = e.first;
      int s = e.second;
      if (vals[to] == -1) {
        vals[to] = vals[vr] ^ s;
        q.push(to);
      } else {
        int nval = vals[vr] ^ s;
        if (vals[to] != nval) return false;
      }
    }
  }
  return true;
}
int SolveWithOffset(int d) {
  memset(__fixed__, -1, sizeof __fixed__);
  for (int i = 0; i < MAXN; ++i) fo[i].clear();
  int up = ((int)(s).size()), down = ((int)(s).size()) - d;
  int l = 0, r = up - 1;
  while (l < r) AddEdge(l, r, 0), ++l, --r;
  l = 0, r = down - 1;
  while (l < r) AddEdge(up + l, up + r, 0), ++l, --r;
  __fixed__[0] = 1;
  __fixed__[0 + up] = 1;
  for (int i = 1; i < d; ++i)
    if (s[i] != '?') {
      int v = s[i] - '0';
      if (__fixed__[i] != -1 && __fixed__[i] != v) return 0;
      __fixed__[i] = v;
    }
  for (int i = d; i < ((int)(s).size()); ++i) {
    if (s[i] == '?') continue;
    if (s[i] == '0') AddEdge(i, up + i - d, 0);
    if (s[i] == '1') AddEdge(i, up + i - d, 1);
  }
  int ans = 1;
  memset(used, 0, sizeof used);
  for (int i = 0; i < up + down; ++i) {
    if (used[i]) continue;
    comp.clear();
    Dfs(i);
    int poss = 0;
    for (int e : comp) vals[e] = -1;
    if (SetVal(i, 0)) ++poss;
    for (int e : comp) vals[e] = -1;
    if (SetVal(i, 1)) ++poss;
    ans = Mult(ans, poss);
  }
  return ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  int ans = 0;
  cin >> s;
  for (int d = 1; d < ((int)(s).size()); ++d) AddTo(ans, SolveWithOffset(d));
  cout << ans << '\n';
  return 0;
}