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 N = 2010;
const int INF = 0x3f3f3f3f;
const int iinf = 1 << 30;
const long long linf = 2e18;
const int mod = 998244353;
const double eps = 1e-7;
void douout(double x) { printf("%lf\n", x + 0.0000000001); }
template <class T>
void print(T a) {
  cout << a << endl;
  exit(0);
}
template <class T>
void chmin(T &a, T b) {
  if (a > b) a = b;
}
template <class T>
void chmax(T &a, T b) {
  if (a < b) a = b;
}
void add(int &a, int b) { a = a + b < mod ? a + b : a + b - mod; }
void sub(int &a, int b) { a = (a - b + mod) % mod; }
void mul(int &a, int b) { a = (long long)a * b % mod; }
int addv(int a, int b) { return (a += b) >= mod ? a -= mod : a; }
int subv(int a, int b) { return (a -= b) < 0 ? a += mod : a; }
int mulv(int a, int b) { return (long long)a * b % mod; }
int read() {
  int f = 1, x = 0;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
int pw(int a, int b) {
  int s = 1;
  for (; b; b >>= 1, a = (long long)a * a % mod)
    if (b & 1) s = (long long)s * a % mod;
  return s;
}
char s[N];
int ans, n;
vector<pair<int, int> > e[N];
int col[N], vis[N];
int flg = 1;
int dfs(int x) {
  for (int i = (0); i <= (((int)e[x].size()) - 1); i++) {
    int to = e[x][i].first;
    if (col[to] == -1) {
      col[to] = (col[x] ^ e[x][i].second);
      if (!dfs(to)) return 0;
    } else {
      if ((col[to] ^ e[x][i].second) != col[x]) return 0;
    }
  }
  return 1;
}
int solve(int m) {
  bool flg = 1;
  int val = 0;
  for (int i = (1); i <= (n + m); i++) e[i].clear();
  memset(col, -1, sizeof(col));
  for (int i = (1); i <= (n / 2); i++) {
    e[i].push_back(make_pair(n - i + 1, 0));
    e[n - i + 1].push_back(make_pair(i, 0));
  }
  for (int i = (1); i <= (m / 2); i++) {
    e[n + i].push_back(make_pair(n + (m - i + 1), 0));
    e[n + (m - i + 1)].push_back(make_pair(n + i, 0));
  }
  for (int i = (1); i <= (m); i++)
    if (s[i] != '?') {
      int v = s[i] - '0';
      e[i].push_back(make_pair(n + i, v));
      e[n + i].push_back(make_pair(i, v));
    }
  for (int i = (m + 1); i <= (n); i++)
    if (s[i] != '?') {
      if (col[i] == -1) {
        col[i] = s[i] - '0';
        if (!dfs(i)) flg = 0;
      } else {
        if (col[i] != s[i] - '0') flg = 0;
      }
      if (!flg) break;
    }
  for (int i = (1); i <= (n + m); i++) {
    if (col[i] == -1) {
      col[i] = 0;
      if (!dfs(i)) flg = 0;
      val++;
    }
    if (!flg) break;
  }
  if (flg)
    return pw(2, val);
  else
    return 0;
}
signed main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  s[n] = '0';
  for (int i = (1); i <= (n - 1); i++) {
    add(ans, solve(i));
  }
  printf("%d\n", ans);
  return 0;
}