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;
int n;
char s[1010];
vector<int> g1[1010 * 2];
vector<int> g2[1010 * 2];
int cc[1010 * 2], cv;
int color[1010 * 2];
void dfs(int c, int w) {
  cc[c] = w;
  for (int i : g1[c]) {
    if (cc[i] == -1) {
      dfs(i, w);
    }
  }
}
bool bipartite(int c, int col) {
  color[c] = col;
  bool ok = true;
  for (int i : g2[c]) {
    if (color[i] == 0) {
      ok = ok && bipartite(i, -col);
      if (!ok) return false;
    } else {
      if (color[i] == color[c]) return false;
    }
  }
  return ok;
}
long long solve(int al) {
  for (int i = 0; i < n + al + 1; i++) {
    g1[i].clear();
    g2[i].clear();
  }
  for (int i = 0; i < al; i++) {
    int ol = al - 1 - i;
    if (i >= ol) break;
    g1[n + i].push_back(n + ol);
    g1[n + ol].push_back(n + i);
  }
  g1[n].push_back(0);
  g1[0].push_back(n);
  for (int i = 0; i < n; i++) {
    int ol = n - 1 - i;
    if (i >= ol) break;
    g1[i].push_back(ol);
    g1[ol].push_back(i);
  }
  vector<pair<int, int> > edges;
  for (int i = 0; i < al; i++) {
    if (s[n - 1 - i] == '0') {
      g1[i + n].push_back(i);
      g1[i].push_back(i + n);
    } else if (s[n - 1 - i] == '1') {
      edges.push_back(make_pair(i, i + n));
    }
  }
  for (int i = al; i < n; i++) {
    int ind = n - 1 - i;
    if (s[ind] == '1') {
      g1[n - 1].push_back(i);
      g1[i].push_back(n - 1);
    } else if (s[ind] == '0') {
      edges.push_back(make_pair(i, n - 1));
    }
  }
  edges.push_back(make_pair(n - 1, n + al));
  for (int i = 0; i <= n + al; i++) {
    cc[i] = -1;
    color[i] = 0;
  }
  cv = 0;
  for (int i = 0; i <= n + al; i++) {
    if (cc[i] != -1) continue;
    dfs(i, cv++);
  }
  for (auto i : edges) {
    if (cc[i.first] == cc[i.second]) {
      return 0;
    }
    g2[cc[i.first]].push_back(cc[i.second]);
    g2[cc[i.second]].push_back(cc[i.first]);
  }
  long long ans = 1;
  for (int i = 0; i < cv; i++) {
    if (color[i]) continue;
    if (bipartite(i, 1)) {
      ans *= 2;
      ans %= 998244353;
    } else
      return 0;
  }
  return ans;
}
int main() {
  scanf("%s", s);
  n = strlen(s);
  long long res = 0;
  for (int i = 1; i < n; i++) {
    res += solve(i);
  }
  res %= 998244353;
  res *= 499122177;
  res %= 998244353;
  printf("%lld\n", res);
}