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;
template <class t>
inline t read(t &x) {
  char c = getchar();
  bool f = 0;
  x = 0;
  while (!isdigit(c)) f |= c == '-', c = getchar();
  while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
  if (f) x = -x;
  return x;
}
template <class t, class... A>
inline void read(t &x, A &...a) {
  read(x);
  read(a...);
}
template <class t>
inline void write(t x) {
  if (x < 0)
    putchar('-'), write(-x);
  else {
    if (x > 9) write(x / 10);
    putchar('0' + x % 10);
  }
}
const int N = 2005, mod = 998244353;
int pw[N], id[N], col[N], idn, fl, n, ans, bl, wh;
vector<pair<int, int> > g[N];
char s[N];
void reset() {
  for (int i = 1; i <= wh; i++) id[i] = 0, col[i] = -1, g[i].clear();
  idn = fl = 0;
}
void emplace_back(int first, int second, int o) {
  g[first].emplace_back(second, o);
  g[second].emplace_back(first, o);
}
void dfs(int first, int o) {
  if (fl) return;
  col[first] = o;
  id[first] = idn;
  for (auto e : g[first]) {
    if (!id[e.first]) {
      dfs(e.first, o ^ e.second);
    } else {
      if ((o ^ e.second) != col[e.first]) fl = 1;
    }
  }
}
signed main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  pw[0] = 1;
  for (int i = 1; i <= n << 1; i++) pw[i] = pw[i - 1] * 2 % mod;
  bl = n << 1 | 1, wh = bl + 1;
  for (int i = 1; i <= n; i++) {
    reset();
    emplace_back(bl, wh, 1);
    emplace_back(bl, 1 + n, 0);
    for (int i = 1, j = n; i < j; i++, j--) emplace_back(i + n, j + n, 0);
    for (int j = 1; j < i; j++) {
      emplace_back(wh, j, 0);
      if (s[j] == '0') emplace_back(wh, j + n, 0);
      if (s[j] == '1') emplace_back(bl, j + n, 0);
    }
    emplace_back(bl, i, 0);
    for (int l = i, r = n; l < r; l++, r--) emplace_back(l, r, 0);
    for (int j = i; j <= n; j++) {
      if (s[j] == '0') emplace_back(j, j + n, 0);
      if (s[j] == '1') emplace_back(j, j + n, 1);
    }
    for (int j = 1; j <= wh; j++)
      if (!id[j]) idn++, dfs(j, 0);
    if (fl || id[wh] == id[bl] && col[wh] == col[bl]) continue;
    if (id[wh] == id[bl])
      ans = (ans + pw[idn - 1]) % mod;
    else
      ans = (ans + pw[idn - 2]) % mod;
  }
  write(ans);
}