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;
const long long INF = std::numeric_limits<long long>::max();
const int MX = 2101;
const long double PI =
    3.14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651328230664709384460955058223172535940812848111745028410270L;
template <typename T>
pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) {
  return pair<T, T>(a.first + b.first, a.second + b.second);
}
template <typename T>
pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) {
  return pair<T, T>(a.first - b.first, a.second - b.second);
}
template <typename T>
T operator*(const pair<T, T> &a, const pair<T, T> &b) {
  return (a.first * b.first + a.second * b.second);
}
template <typename T>
T operator^(const pair<T, T> &a, const pair<T, T> &b) {
  return (a.first * b.second - a.second * b.first);
}
std::string s;
int N;
vector<vector<int> > ones;
vector<vector<int> > zeros;
inline void add(int a, int b, vector<vector<int> > &kur) {
  kur[a].push_back(b);
  kur[b].push_back(a);
}
vector<bool> buvau;
vector<int> col;
void perzero(int first) {
  buvau[first] = true;
  for (auto u : zeros[first])
    if (!buvau[u]) perzero(u);
}
bool ieskok(int first) {
  for (auto u : zeros[first]) {
    if (col[u] == -1) {
      col[u] = col[first];
      if (!ieskok(u)) return false;
    } else {
      if (col[u] != col[first]) return false;
    }
  }
  for (auto u : ones[first]) {
    if (col[u] == -1) {
      col[u] = !col[first];
      if (!ieskok(u)) return false;
    } else {
      if (col[u] == col[first]) return false;
    }
  }
  return true;
}
vector<long long> P(2 * MX);
void prec() {
  P[0] = 1;
  for (int i = 1; i < 2 * MX; ++i) P[i] = (2 * P[i - 1]) % MOD;
}
long long bandyk(int k) {
  zeros = vector<vector<int> >(MX);
  ones = vector<vector<int> >(MX);
  add(0, 1, ones);
  add(N + 1, 1, zeros);
  add(2 + N + k - 1, 1, zeros);
  add(2, 1, zeros);
  add(N + 2, 1, zeros);
  for (int i = 0; i < N; ++i) {
    if (i >= k) {
      if (s[i] == '1') {
        add(i + 2, 1, zeros);
        add(i + 2, 0, ones);
      } else if (s[i] == '0') {
        add(i + 2, 1, ones);
        add(i + 2, 0, zeros);
      }
    } else {
      if (s[i] == '1') {
        add(2 + i, 2 + N + i, ones);
      } else if (s[i] == '0') {
        add(2 + i, 2 + N + i, zeros);
      }
      if (2 + i != k - i + 1) zeros[2 + N + i].push_back(k - i - 1 + 2 + N);
    }
    if (2 + i != N - i + 1) zeros[2 + i].push_back(N - i - 1 + 2);
  }
  buvau = vector<bool>(MX, false);
  for (int i = 0; i < 2 + N + k; ++i) {
    if (buvau[i]) continue;
    perzero(i);
  }
  long long kiek = -1;
  col = vector<int>(MX, -1);
  for (int i = 0; i < 2 + N + k; ++i) {
    if (col[i] != -1) continue;
    col[i] = 0;
    if (!ieskok(i)) return 0ll;
    kiek++;
  }
  return P[kiek];
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> s;
  prec();
  long long ats = 0;
  N = s.size();
  reverse(s.begin(), s.end());
  for (int i = 1; i < N + 1; ++i) ats = (ats + bandyk(i)) % MOD;
  printf("%lld\n", ats);
}