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 = 0x3f3f3f3f;
const long long INF = 0x3f3f3f3f3f3f3f3f;
const long long mod = 998244353;
const int maxn = 1e3 + 5;
char str[maxn], a[maxn], b[maxn];
int N;
long long ans;
long long qp(long long x, long long n) {
  long long re = 1;
  while (n) {
    if (n & 1) re = re * x % mod;
    x = x * x % mod;
    n >>= 1;
  }
  return re;
}
bool judge(char s[], int n) {
  for (int i = 0, j = n - 1; i < j; i++, j--) {
    if (s[i] != '?' && s[j] != '?' & s[i] != s[j]) return 0;
    if (s[i] != '?' || s[j] != '?') {
      char ch = s[i] == '?' ? s[j] : s[i];
      s[i] = s[j] = ch;
    }
  }
  return 1;
}
void deal(int L) {
  for (int i = 0; i <= L - 1; i++) {
    if (str[i] != '?') {
      if (a[i] == '?' && b[i] == '?') continue;
      if (a[i] == '?' || b[i] == '?') {
        a[i] = b[i] = '!';
        a[N - 1 - i] = b[L - 1 - i] = '!';
        i = min(i, min(N - 1 - i, L - 1 - i)) - 1;
      }
    }
  }
}
void solve(int L) {
  memset((a), 0, sizeof(a));
  memset((b), 0, sizeof(b));
  int l = N - L;
  int p = 0;
  bool oka = 0, okb = 0;
  for (int i = 0; i <= l - 1; i++) a[N - 1 - i] = str[N - 1 - i];
  while (true) {
    for (int t = 0; t <= l - 1; t++) {
      int i = t + p;
      if (L - 1 - i < i) okb = 1;
      if (okb) break;
      a[i] = a[N - 1 - i];
      b[i] = (str[i] == '?' || a[i] == '?')
                 ? '?'
                 : (str[i] - '0') ^ (a[i] - '0') + '0';
      if (i == 0) {
        if (b[i] == '0') return;
        b[i] = '1';
      }
      b[L - 1 - i] = b[i];
      a[L - 1 - i] = (str[L - 1 - i] == '?' || b[L - 1 - i] == '?')
                         ? '?'
                         : (str[L - 1 - i] - '0') ^ (b[L - 1 - i] - '0') + '0';
    }
    if (okb) break;
    p += l;
  }
  if (judge(a, N) && judge(b, L)) {
    deal(L);
    long long cnt = 0;
    for (int i = 0, j = L - 1; i <= j; i++, j--) {
      int c = 0;
      if (a[i] == '?') c++;
      if (b[i] == '?') c++;
      if (str[i] == '?') c++;
      cnt += max(0, (c - 1));
      a[i] = b[i] = a[N - 1 - i] = b[L - 1 - i] = '!';
      deal(L);
    }
    for (int i = 0, j = N - 1; i <= j; i++, j--) {
      if (a[i] == '?') cnt++;
    }
    ans = (ans + qp(2, cnt)) % mod;
  }
}
int main() {
  scanf("%s", str);
  N = strlen(str);
  for (int i = 0; i <= (N - 1) / 2; i++) {
    swap(str[i], str[N - 1 - i]);
  }
  for (int i = 1; i <= N - 1; i++) {
    solve(i);
  }
  printf("%lld\n", ans);
}