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 inf = (int)1e9;
const long long INF = (long long)5e18;
const int MOD = 998244353;
int _abs(int x) { return x < 0 ? -x : x; }
int add(int x, int y) {
  x += y;
  return x >= MOD ? x - MOD : x;
}
int sub(int x, int y) {
  x -= y;
  return x < 0 ? x + MOD : x;
}
void Add(int &x, int y) {
  x += y;
  if (x >= MOD) x -= MOD;
}
void Sub(int &x, int y) {
  x -= y;
  if (x < 0) x += MOD;
}
void Mul(int &x, int y) { x = (long long)(x) * (y) % MOD; }
int qpow(int x, int y) {
  int ret = 1;
  while (y) {
    if (y & 1) ret = (long long)(ret) * (x) % MOD;
    x = (long long)(x) * (x) % MOD;
    y >>= 1;
  }
  return ret;
}
void checkmin(int &x, int y) {
  if (x > y) x = y;
}
void checkmax(int &x, int y) {
  if (x < y) x = y;
}
void checkmin(long long &x, long long y) {
  if (x > y) x = y;
}
void checkmax(long long &x, long long y) {
  if (x < y) x = y;
}
inline int read() {
  int x = 0, f = 1;
  char c = getchar();
  while (c > '9' || c < '0') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9')
    x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
  return x * f;
}
const int N = 1005;
int a[N], b[N], n, ans = 0, flag, st;
char s[N];
void insb(int pos, int c);
void insa(int pos, int c) {
  if (a[pos] != -1) {
    if (a[pos] != c) flag = 0;
    return;
  }
  a[pos] = c;
  if (s[pos] != '?' && pos >= st) insb(pos, c ^ (s[pos] - '0'));
  if (a[n + 1 - pos] == -1) insa(n + 1 - pos, c);
}
void insb(int pos, int c) {
  if (b[pos] != -1) {
    if (b[pos] != c) flag = 0;
    return;
  }
  b[pos] = c;
  if (s[pos] != '?') insa(pos, c ^ (s[pos] - '0'));
  if (b[n + st - pos] == -1) insb(n + st - pos, c);
}
int main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  for (st = 2; st <= n; st++) {
    memset(a, -1, sizeof(a));
    memset(b, -1, sizeof(b));
    flag = 1;
    for (int i = 1; i < st; i++)
      if (s[i] != '?') insa(i, s[i] - '0');
    insb(st, 1);
    if (!flag) continue;
    int now = 1;
    for (int i = 1; i <= n; i++)
      if (a[i] == -1) insa(i, 1), Mul(now, 2);
    for (int i = st; i <= n; i++)
      if (b[i] == -1) insb(i, 1), Mul(now, 2);
    Add(ans, now);
  }
  cout << ans << endl;
  return 0;
}