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 pow_mod(long long a, long long b, long long m) {
  if (b == 0) return 1;
  long long x = pow_mod(a, b / 2, m);
  x = (x * x) % m;
  if (b % 2 != 0) x = (x * a) % m;
  return x;
}
bool bicolor(const vector<vector<pair<int, int> > >& g, vector<int>& col,
             int u) {
  for (int i = 0; i < int(g[u].size()); ++i) {
    int v = g[u][i].first;
    int x = g[u][i].second;
    if (col[v] < 0) {
      col[v] = col[u] ^ x;
      if (!bicolor(g, col, v)) return false;
    } else if (col[v] != (col[u] ^ x)) {
      return false;
    }
  }
  return true;
}
int main() {
  ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  const long long P = 998244353;
  string s;
  cin >> s;
  int m = int(s.size());
  long long ans = 0;
  for (int n = 1; n < m; ++n) {
    vector<vector<pair<int, int> > > g(2 * m);
    g[0].push_back(pair<int, int>(m + m - n, 0));
    g[m + m - n].push_back(pair<int, int>(0, 0));
    for (int i = 0; i < m / 2; ++i) {
      int u = i;
      int v = m - 1 - i;
      g[u].push_back(pair<int, int>(v, 0));
      g[v].push_back(pair<int, int>(u, 0));
    }
    for (int i = 0; i < n / 2; ++i) {
      int u = m + m - n + i;
      int v = m + m - 1 - i;
      g[u].push_back(pair<int, int>(v, 0));
      g[v].push_back(pair<int, int>(u, 0));
    }
    for (int i = 0; i < m - n; ++i) {
      int u = 0;
      int v = m + i;
      g[u].push_back(pair<int, int>(v, 1));
      g[v].push_back(pair<int, int>(u, 1));
    }
    for (int i = 0; i < m; ++i) {
      if (s[i] != '?') {
        int u = i;
        int v = m + i;
        g[u].push_back(pair<int, int>(v, int(s[i] - '0')));
        g[v].push_back(pair<int, int>(u, int(s[i] - '0')));
      }
    }
    vector<int> col(g.size(), -1);
    int ncomp = 0;
    bool ok = true;
    for (int i = 0; i < int(g.size()) && ok; ++i) {
      if (col[i] < 0) {
        ++ncomp;
        col[i] = 0;
        if (!bicolor(g, col, i)) ok = false;
      }
    }
    if (ok) {
      ans = (ans + pow_mod(2, ncomp - 1, P)) % P;
    }
  }
  cout << ans << endl;
}