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 double pi = acos(-1.0);
const double eps = 1e-11;
template <class T>
inline void ckmin(T& a, T b) {
  if (b < a) a = b;
}
template <class T>
inline void ckmax(T& a, T b) {
  if (b > a) a = b;
}
template <class T>
inline T sqr(T x) {
  return x * x;
}
using VI = vector<int>;
template <typename base_type, base_type _MOD>
class IntMod {
 public:
  static const int INVERSE_CACHE_SIZE = (1 << 20);
  static base_type MOD;
  static void set_mod(base_type new_mod) { MOD = new_mod; }
  base_type n;
  IntMod(long long d = 0) { n = (d >= 0 ? d % MOD : (d % MOD + MOD) % MOD); }
  virtual ~IntMod() = default;
  IntMod operator-() const { return build(n == 0 ? 0 : MOD - n); }
  IntMod& operator+=(IntMod a) {
    n = (n >= MOD - a.n ? n - MOD + a.n : n + a.n);
    return *this;
  }
  IntMod& operator-=(IntMod a) {
    n = (n >= a.n) ? n - a.n : n - a.n + MOD;
    return *this;
  }
  IntMod& operator*=(IntMod a) {
    *this = *this * a;
    return *this;
  }
  IntMod& operator/=(IntMod a) {
    *this = *this / a;
    return *this;
  }
  static IntMod build(base_type n) {
    IntMod r;
    r.n = n;
    return r;
  }
  static base_type inverse_cache[INVERSE_CACHE_SIZE];
  static bool inverse_cache_ready;
  friend IntMod inverse(IntMod n) { return build(inverse_internal(n.n)); }
  static base_type inverse_internal(base_type n) {
    if (!inverse_cache_ready) {
      inverse_cache_ready = true;
      inverse_cache[0] = 0;
      inverse_cache[1] = 1;
      for (int n = 2; n < INVERSE_CACHE_SIZE; ++n)
        inverse_cache[n] =
            (MOD -
             (base_type)((long long)inverse_cache[MOD % n] * (MOD / n) % MOD));
    }
    return n < INVERSE_CACHE_SIZE
               ? inverse_cache[n]
               : MOD - (base_type)((long long)inverse_internal(MOD % n) *
                                   (MOD / n) % MOD);
  }
  friend bool operator==(IntMod a, IntMod b) { return a.n == b.n; }
  friend bool operator!=(IntMod a, IntMod b) { return a.n != b.n; }
  friend IntMod operator+(IntMod a, IntMod b) {
    return build(a.n >= MOD - b.n ? a.n - MOD + b.n : a.n + b.n);
  }
  friend IntMod operator-(IntMod a, IntMod b) {
    return build(a.n >= b.n ? a.n - b.n : a.n - b.n + MOD);
  }
  friend IntMod operator*(IntMod a, IntMod b) {
    return build(
        static_cast<base_type>(static_cast<long long>(a.n) * b.n % MOD));
  }
  friend IntMod operator/(IntMod a, IntMod b) { return a * inverse(b); }
  friend IntMod pow(IntMod p, long long e) {
    if (e <= 0) return IntMod(1);
    IntMod r = IntMod(1);
    while (1) {
      if (e & 1) r *= p;
      e /= 2;
      if (e)
        p = p * p;
      else
        break;
    }
    return r;
  }
};
template <typename base_type, base_type _MOD>
base_type IntMod<base_type, _MOD>::inverse_cache[INVERSE_CACHE_SIZE];
template <typename base_type, base_type _MOD>
bool IntMod<base_type, _MOD>::inverse_cache_ready;
template <typename base_type, base_type _MOD>
base_type IntMod<base_type, _MOD>::MOD = _MOD;
using Int = IntMod<int, 998244353>;
int n;
string str;
VI s;
int length[2];
VI f, g;
int ID(int p, int b) { return p * 2 + b; }
int getf(int p) {
  if (f[p] < 0) return p;
  int r = getf(f[p]);
  g[p] ^= g[f[p]];
  f[p] = r;
  return r;
}
bool add(int a, int b, int delta) {
  int pa = getf(a);
  int pb = getf(b);
  if (pa == pb) return delta == (g[a] ^ g[b]);
  f[pa] = pb;
  g[pa] = (delta ^ g[a] ^ g[b]);
  return true;
}
Int solve(int la, int lb) {
  length[0] = la;
  length[1] = lb;
  f = VI(n * 2 + 1, -1);
  g = VI(n * 2 + 1, 0);
  for (int b = 0; b < (2); ++b)
    if (!add(ID(length[b] - 1, b), n * 2, 1)) return 0;
  for (int b = 0; b < (2); ++b)
    for (int i = (length[b]); i < (n); ++i)
      if (!add(ID(i, b), n * 2, 0)) return 0;
  for (int b = 0; b < (2); ++b)
    for (int i = 0; i < (length[b]); ++i)
      if (!add(ID(i, b), ID(length[b] - 1 - i, b), 0)) return 0;
  for (int i = 0; i < (n); ++i)
    if (s[i] >= 0 && !add(ID(i, 0), ID(i, 1), s[i])) return 0;
  Int ret = 1;
  for (int i = 0; i < (n * 2 + 1); ++i)
    if (f[i] < 0) ret *= 2;
  ret /= 2;
  return ret;
}
int main() {
  std::ios::sync_with_stdio(false);
  while (cin >> str) {
    n = ((int)str.length());
    s = VI(n);
    for (int i = 0; i < (n); ++i) s[i] = (str[i] == '?' ? -1 : str[i] - '0');
    reverse(s.begin(), s.end());
    Int ret = 0;
    for (int l1 = (1); l1 < (n); ++l1) {
      Int t = solve(l1, n);
      ret += t;
    }
    printf("%d\n", ret.n);
    break;
  }
  return 0;
}