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 M = 998244353;
long long rep(long long x) {
  x %= M;
  if (x < 0) x += M;
  return x;
}
long long pw(long long a, long long b) {
  long long r = 1;
  while (b) {
    if (b & 1) r = rep(r * a);
    a = rep(a * a), b /= 2;
  }
  return r;
}
long long dv(long long a, long long b) { return rep(a * pw(b, M - 2)); }
struct T {
  long long n;
  vector<long long> force;
  vector<bool> vis;
  bool wrong;
  vector<vector<pair<long long, long long>>> g;
  T(long long nn) {
    wrong = 0;
    n = nn;
    force.clear();
    vis.clear();
    g.clear();
    vis.resize(n, 0);
    force.resize(n, -1);
    g.resize(n);
  }
  void add(long long x, long long a) {
    assert(1 <= x && x <= n);
    x--;
    if (force[x] != -1 && force[x] != a) {
      wrong = 1;
    }
    force[x] = a;
  }
  void add(long long x, long long y, long long a) {
    assert(1 <= x && x <= n);
    assert(1 <= y && y <= n);
    x--, y--;
    g[x].push_back({y, a});
    g[y].push_back({x, a});
  }
  long long ret;
  void dfs(long long a) {
    vis[a] = 1;
    for (auto &it : g[a]) {
      long long b = it.first, c = it.second ^ force[a];
      if (force[b] != -1 && force[b] != c) {
        ret = 0;
      }
      force[b] = c;
      if (!vis[b]) {
        dfs(b);
      }
    }
  }
  long long cnt() {
    if (wrong) return 0;
    ret = 1;
    for (long long i = 0; i < n; i++) {
      if (!vis[i] && force[i] != -1) {
        dfs(i);
        if (ret == 0) return 0;
      }
    }
    for (long long i = 0; i < n; i++) {
      if (!vis[i] && force[i] == -1) {
        force[i] = 0;
        dfs(i);
        ret = rep(ret * 2);
        if (ret == 0) return 0;
      }
    }
    return ret;
  }
};
string s;
long long n;
long long ret;
bool match0 = 1;
long long pre0;
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> s;
  n = (long long)s.size();
  s = " " + s;
  for (long long i = 1; i <= n; i++)
    if (s[i] == '1') match0 = 0;
  for (long long i = 1; i <= n; i++) {
    if (s[i] == '1') break;
    pre0++;
  }
  for (long long l1 = 1; l1 < n; l1++) {
    for (long long l2 = n; l2 <= n; l2++) {
      long long start1 = n - l1 + 1, start2 = n - l2 + 1;
      T f(l1 + l2);
      f.add(1, 1);
      f.add(l1 + 1, 1);
      for (long long i = 1; i <= l1; i++) f.add(i, l1 - i + 1, 0);
      for (long long i = 1; i <= l2; i++) f.add(l1 + i, l1 + l2 - i + 1, 0);
      bool wrong = 0;
      for (long long i = 1; i <= n; i++) {
        bool is1 = (i >= start1);
        bool is2 = (i >= start2);
        if (s[i] != '?') {
          if (is1 && is2) {
            f.add(i - start1 + 1, l1 + i - start2 + 1, s[i] - '0');
          }
          if (is1 && !is2) {
            f.add(i - start1 + 1, s[i] - '0');
          }
          if (!is1 && is2) {
            f.add(l1 + i - start2 + 1, s[i] - '0');
          }
          if (!is1 && !is2) {
            if (s[i] == '1') wrong = 1;
          }
        }
      }
      if (wrong) continue;
      if (f.wrong) continue;
      long long nemo = f.cnt();
      if (nemo) {
        ret = rep(ret + nemo);
      }
    }
  }
  cout << ret << "\n";
}