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;
string s;
int m, n, n0, n1;
bool check(const vector<vector<pair<int, int> > > &g, int u, int cc,
           vector<int> &c) {
  c[u] = 1;
  for (int i = 0; i < g[u].size(); i++) {
    int v = g[u][i].first;
    if (g[u][i].second == 0) {
      if (v == n0 && cc != 0 || v == n1 && cc != 1) return false;
      if (!c[v] && !check(g, v, cc, c)) return false;
    } else {
      if (v == n0 && cc != 1 || v == n1 && cc != 0) return false;
      if (!c[v] && !check(g, v, cc ^ 1, c)) return false;
    }
  }
  return true;
}
bool check(const vector<vector<pair<int, int> > > &g) {
  vector<int> colors(n);
  return check(g, n0, 0, colors);
}
void dfs(const vector<vector<pair<int, int> > > &g, int u, vector<int> &c) {
  c[u] = 1;
  for (int i = 0; i < g[u].size(); i++)
    if (!c[g[u][i].first]) dfs(g, g[u][i].first, c);
}
long long solve(int k) {
  n = m + k + 2;
  n0 = m + k, n1 = m + k + 1;
  vector<vector<pair<int, int> > > g(n, vector<pair<int, int> >());
  g[n0].push_back(make_pair(n1, 1));
  g[n1].push_back(make_pair(n0, 1));
  for (int i = 0, j = m - 1; i < j; i++, j--) {
    g[i].push_back(make_pair(j, 0));
    g[j].push_back(make_pair(i, 0));
  }
  for (int i = 0, j = k - 1; i < j; i++, j--) {
    g[m + i].push_back(make_pair(m + j, 0));
    g[m + j].push_back(make_pair(m + i, 0));
  }
  g[m - 1].push_back(make_pair(n1, 0));
  g[n1].push_back(make_pair(m - 1, 0));
  g[m + k - 1].push_back(make_pair(n1, 0));
  g[n1].push_back(make_pair(m + k - 1, 0));
  for (int i = 0; i < m; i++) {
    if (s[m - i - 1] == '0') {
      if (i < k) {
        g[i].push_back(make_pair(m + i, 0));
        g[m + i].push_back(make_pair(i, 0));
      } else {
        g[i].push_back(make_pair(n0, 0));
        g[n0].push_back(make_pair(i, 0));
      }
    } else if (s[m - i - 1] == '1') {
      if (i < k) {
        g[i].push_back(make_pair(m + i, 1));
        g[m + i].push_back(make_pair(i, 1));
      } else {
        g[i].push_back(make_pair(n1, 0));
        g[n1].push_back(make_pair(i, 0));
      }
    }
  }
  if (!check(g)) return 0;
  int c = 0;
  vector<int> colors(n, 0);
  for (int i = 0; i < n; i++)
    if (!colors[i]) {
      dfs(g, i, colors);
      c++;
    }
  c--;
  long long sum = 1;
  for (long long t = 2; c; c >>= 1, t = (t * t) % 998244353)
    if (c & 1) sum = (sum * t) % 998244353;
  return sum;
}
int main(int argc, char *argv[]) {
  cin >> s;
  m = (int)s.size();
  if (s[m - 1] == '?') s[m - 1] = '0';
  long long ans = 0;
  if (s[m - 1] == '0')
    for (int i = 1; i < m; i++) ans = (ans += solve(i)) % 998244353;
  cout << ans << endl;
  return 0;
}