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;
const int maxn = 10500;
string s;
int m;
vector<int> g[maxn], rg[maxn];
int n, cnt;
int mrk[maxn], usd[maxn];
bool has[5050][5050];
inline void link(int x, int y) {
  if (mrk[x] == -1) mrk[x] = n++;
  if (mrk[y] == -1) mrk[y] = n++;
  if (has[mrk[x]][mrk[y]]) return;
  rg[mrk[x]].emplace_back(mrk[y]);
  rg[mrk[y]].emplace_back(mrk[x]);
  has[mrk[x]][mrk[y]] = 1;
}
inline void colo(int x, int c) {
  if (usd[x]) {
    if (usd[x] != c + 1) cnt = -1;
    return;
  }
  usd[x] = c + 1;
  for (int i = 0; i < rg[x].size() && ~cnt; i++) {
    if (!usd[rg[x][i]])
      colo(rg[x][i], c ^ 1);
    else if (usd[rg[x][i]] != (c ^ 1) + 1) {
      cnt = -1;
      return;
    }
  }
}
inline void addedge(int x, int y) {
  g[x].emplace_back(y);
  g[y].emplace_back(x);
}
inline void remedge(int x, int y) {
  g[x].pop_back();
  g[y].pop_back();
}
int ans;
inline void add(int &a, int b) {
  a += b;
  if (a >= 998244353) a -= 998244353;
}
int fa[maxn];
inline int getfa(int x) { return fa[x] == x ? x : fa[x] = getfa(fa[x]); }
inline void Union(int x, int y) {
  x = getfa(x), y = getfa(y);
  if (x == y) return;
  fa[x] = y;
}
int pw2[maxn];
int calc(int fst) {
  for (int i = 0; i < m * 4; i++) fa[i] = i;
  for (int i = 0; i < m * 4; i++)
    for (int j = 0; j < g[i].size(); j++) Union(i, g[i][j]);
  for (int i = 0; i < m; i++)
    if (getfa(i) == getfa(m + i)) {
      return 0;
    } else if (getfa(m * 2 + i) == getfa(m * 3 + i)) {
      return 0;
    }
  memset(mrk, -1, sizeof(mrk));
  n = 0;
  for (int i = 0; i < m; i++) {
    link(getfa(i), getfa(m + i));
    link(getfa(m * 2 + i), getfa(m * 3 + i));
  }
  memset(usd, 0, sizeof(usd));
  cnt = 0;
  colo(mrk[getfa(m)], 1);
  for (int i = 0; i < fst; i++) colo(mrk[getfa(m * 2 + i)], 1);
  colo(mrk[getfa(m * 3 + fst)], 1);
  if (cnt == -1) return 0;
  for (int i = 0; i < n; i++)
    if (!usd[i]) {
      cnt++;
      colo(i, 1);
    }
  for (int i = 0; i < n; i++) rg[i].clear();
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) has[i][j] = 0;
  return pw2[cnt];
}
int main() {
  pw2[0] = 1;
  for (int i = 1; i < maxn; i++) pw2[i] = pw2[i - 1] * 2ll % 998244353;
  cin >> s;
  m = s.length();
  for (int i = 0; i < m; i++) {
    if (m - 1 - i > i) {
      addedge(i, m - 1 - i);
      addedge(m + i, m + m - 1 - i);
    }
    if (s[i] == '0') {
      addedge(i, m + m + i);
      addedge(m + i, m + m + m + i);
    } else if (s[i] == '1') {
      addedge(i, m * 3 + i);
      addedge(m + i, m * 2 + i);
    }
  }
  for (int fst = 1; fst < m; fst++) {
    for (int i = 0; fst + i < m; i++) {
      if (m - 1 - i > fst + i) {
        addedge(2 * m + fst + i, 2 * m + m - 1 - i);
        addedge(3 * m + fst + i, 3 * m + m - 1 - i);
      }
    }
    add(ans, calc(fst));
    for (int i = 0; fst + i < m; i++) {
      if (m - 1 - i > fst + i) {
        remedge(2 * m + fst + i, 2 * m + m - 1 - i);
        remedge(3 * m + fst + i, 3 * m + m - 1 - i);
      }
    }
  }
  cout << ans;
  return 0;
}