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;
template <typename T, typename U>
string to_string(const pair<T, U>& pr) {
  return "(" + to_string(pr.first) + "," + to_string(pr.second) + ")";
}
template <typename T>
string to_string(const vector<T>& vc, int w) {
  if (vc.empty()) return "";
  if (w + 1 == vc.size()) return to_string(vc[w]);
  return to_string(vc[w]) + "," + to_string(vc, w + 1);
}
template <typename T>
string to_string(const vector<T>& vc) {
  return "{" + to_string(vc, 0) + "}";
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
class DebugStream {
} LOG;
template <typename T>
DebugStream& operator<<(DebugStream& s, const T&) {
  return s;
}
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 1e5 + 9, maxV = 1e6 + 9, MOD = 998244353, SQ = 335, lg = 20,
          bs = 29;
string str;
int n;
int get(vector<int>& cmp, int u) {
  if (cmp[u] != u) cmp[u] = get(cmp, cmp[u]);
  return cmp[u];
}
bool dfs(vector<int>& sd, const vector<vector<int>>& adj, int nd) {
  assert(sd[nd] != -1);
  for (auto el : adj[nd]) {
    if (sd[el] != -1) {
      if (sd[el] == sd[nd]) return false;
    } else {
      sd[el] = sd[nd] ^ 1;
      if (!dfs(sd, adj, el)) return false;
    }
  }
  return true;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> str;
  for (auto& el : str) el -= '0';
  n = str.size();
  long long ans = 0;
  for (int u = 1; u < n; u++) {
    int sz = n - u;
    vector<int> cmp(n + sz), inds;
    iota(cmp.begin(), cmp.end(), 0);
    vector<vector<pair<long long, long long>>> edg(2);
    for (int i = 0; i < u; i++)
      if (str[i] == 0 || str[i] == 1) inds.push_back(i);
    for (int i = 1; i < inds.size(); i++) {
      int a = inds[i - 1], b = inds[i];
      edg[str[a] ^ str[b]].emplace_back(a, b);
    }
    for (int i = 0; i < n / 2; i++) edg[0].emplace_back(i, n - 1 - i);
    for (int i = 0; i < sz / 2; i++)
      edg[0].emplace_back(n + i, n + (sz - 1 - i));
    for (int i = 0; i < sz; i++) {
      char cr = str[u + i];
      if (cr == 0 || cr == 1) edg[cr].emplace_back(u + i, n + i);
    }
    edg[0].emplace_back(0, n);
    for (auto el : edg[0]) {
      int a = get(cmp, el.first), b = get(cmp, el.second);
      if (a != b) cmp[b] = a;
    }
    vector<vector<int>> adj(cmp.size());
    for (auto& el : edg[1]) {
      el.first = get(cmp, el.first);
      el.second = get(cmp, el.second);
      adj[el.first].push_back(el.second);
      adj[el.second].push_back(el.first);
    }
    vector<int> sd(cmp.size(), -1);
    long long cr = 1;
    for (int i = 0; i < cmp.size(); i++) {
      if (get(cmp, i) != i || sd[i] != -1) continue;
      sd[i] = 0;
      if (!dfs(sd, adj, i)) cr = 0;
      cr = cr * 2 % MOD;
    }
    cr = cr * 499122177 % MOD;
    ans = (ans + cr) % MOD;
  }
  cout << ans << '\n';
}