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 void rd(T &x) {
  x = 0;
  char c = getchar();
  int f = 1;
  while (!isdigit(c)) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (isdigit(c)) x = x * 10 - '0' + c, c = getchar();
  x *= f;
}
const int N = 2010, mod = 998244353;
int Pow(int x, int y) {
  int res = 1;
  while (y) {
    if (y & 1) res = res * (long long)x % mod;
    x = x * (long long)x % mod, y >>= 1;
  }
  return res;
}
int Ans;
int fa[N];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void un(int x, int y) {
  int fx = find(x), fy = find(y);
  if (fx == fy) return;
  fa[fx] = fy;
}
struct ed {
  int x, y;
  ed(int x = 0, int y = 0) : x(x), y(y) {}
};
vector<ed> e[2];
vector<int> G[N];
int col[N], flg;
void getcol(int u, int c) {
  col[u] = c;
  for (int i = 0; i < G[u].size(); ++i) {
    int v = G[u][i];
    if (!col[v])
      getcol(v, -c);
    else if (col[v] != -c)
      flg = 0;
    if (!flg) return;
  }
}
void check(int n, int id0, int id1) {
  for (int i = 1; i <= n; ++i) fa[i] = i, col[i] = 0, G[i].clear();
  for (int i = 0; i < e[0].size(); ++i) un(e[0][i].x, e[0][i].y);
  if (find(id0) == find(id1)) return;
  for (int i = 0; i < e[1].size(); ++i) {
    int x = find(e[1][i].x), y = find(e[1][i].y);
    G[x].push_back(y), G[y].push_back(x);
  }
  flg = 1;
  for (int i = 1; i <= n && flg; ++i)
    if (col[i] == 0) getcol(i, 1);
  if (!flg) return;
  for (int i = 0; i < e[1].size(); ++i) un(e[1][i].x, e[1][i].y);
  int cnt = 0;
  for (int i = 1; i <= n; ++i)
    if (find(i) == i) cnt++;
  Ans = (Ans + Pow(2, cnt - 1)) % mod;
}
char str[N];
int n;
void build(int m) {
  int id0 = n + m + 1, id1 = n + m + 2;
  e[0].clear(), e[1].clear();
  for (int i = 1; i * 2 <= n; ++i) e[0].push_back(ed(i, n - i + 1));
  for (int i = 1; i * 2 <= m; ++i) e[0].push_back(ed(n + i, n + m - i + 1));
  e[0].push_back(ed(n + 1, id1));
  for (int i = 1; i <= n; ++i) {
    if (str[i] == '?') continue;
    if (i <= n - m)
      e[0].push_back(ed(i, str[i] == '0' ? id0 : id1));
    else
      e[str[i] - '0'].push_back(ed(i, i - (n - m) + n));
  }
  e[1].push_back(ed(id0, id1));
  check(n + m + 2, id0, id1);
}
int main() {
  scanf("%s", str + 1);
  n = strlen(str + 1);
  for (int i = 1; i < n; ++i) build(i);
  printf("%d", Ans);
  return 0;
}