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;
long long mod = 998244353;
vector<int> graph[2001];
vector<int> parent(2001);
vector<int> vis(2001);
vector<int> sz(2001);
vector<int> val(2001);
int root(int x) {
  while (parent[x] != x) {
    parent[x] = parent[parent[x]];
    x = parent[x];
  }
  return x;
}
void merge(int x, int y) {
  int r1 = root(x);
  int r2 = root(y);
  if (r1 == r2) return;
  if (sz[r1] > sz[r2]) {
    parent[r2] = r1;
    sz[r1] += sz[r2];
  } else {
    parent[r1] = r2;
    sz[r2] += sz[r1];
  }
}
bool fix(int i, int j) {
  int x = val[i];
  if (x != -1 && x != j) return 0;
  if (x != -1) return 1;
  queue<int> q;
  q.push(i);
  vis[i] = 1;
  val[i] = j;
  while (!q.empty()) {
    int t = q.front();
    q.pop();
    for (int j = 0; j < graph[t].size(); j++) {
      int y = graph[t][j];
      if (vis[y]) {
        if (val[y] == val[t]) return 0;
        continue;
      }
      val[y] = (val[t] + 1) % 2;
      vis[y] = 1;
      q.push(y);
    }
  }
  return 1;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  string s;
  cin >> s;
  int n = s.size();
  int k = (n + 1) / 2;
  long long ans = 0;
  for (int l = 1; l <= n; l++) {
    int m = (l + 1) / 2;
    bool flag = 1;
    int comp = 0;
    for (int i = 0; i < m + k; i++) {
      parent[i] = i;
      sz[i] = 1;
      vis[i] = 0;
      val[i] = -1;
      graph[i].clear();
    }
    for (int i = 0; i < l; i++) {
      int idx1;
      int idx2;
      if (i >= m) {
        idx1 = l - i - 1 + k;
      } else
        idx1 = i + k;
      if (i >= k) {
        idx2 = n - i - 1;
      } else
        idx2 = i;
      if (s[n - i - 1] == '0') {
        merge(idx2, idx1);
      }
    }
    for (int i = 0; i < l; i++) {
      int idx1;
      int idx2;
      if (i >= m) {
        idx1 = l - i - 1 + k;
      } else
        idx1 = i + k;
      if (i >= k) {
        idx2 = n - i - 1;
      } else
        idx2 = i;
      if (s[n - i - 1] == '1') {
        int r1 = root(idx2);
        int r2 = root(idx1);
        if (r1 == r2) {
          flag = 0;
          break;
        }
        graph[r1].push_back(r2);
        graph[r2].push_back(r1);
      }
    }
    if (!flag) continue;
    for (int j = 0; j < k + m; j++) {
    }
    fix(root(0), 1);
    bool b = fix(root(k), 1);
    if (b == 0) {
      continue;
    }
    for (int i = 0; i < n - l; i++) {
      if (s[i] == '?') continue;
      int idx;
      if (n - i - 1 >= k)
        idx = i;
      else
        idx = n - i - 1;
      if (s[i] == '0') {
        int b = fix(root(idx), 0);
        if (b == 0) {
          flag = 0;
          break;
        }
      }
      if (s[i] == '1') {
        int b = fix(root(idx), 1);
        if (b == 0) {
          flag = 0;
          break;
        }
      }
    }
    if (!flag) continue;
    for (int i = 0; i < k + m; i++) {
      if (vis[root(i)]) continue;
      if (parent[i] != i) continue;
      comp++;
      bool b = fix(i, 1);
      if (b == 0) {
        flag = 0;
        break;
      }
    }
    if (!flag) continue;
    long long temp = 1;
    for (int j = 0; j < comp; j++) temp = (temp * 2) % mod;
    ans = (ans + temp) % mod;
  }
  cout << ans << endl;
}