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>
int dsu[1000 * 4];
char marked[1000 * 4];
int find(int i) { return dsu[i] < 0 ? i : (dsu[i] = find(dsu[i])); }
void join(int i, int j) {
  i = find(i);
  j = find(j);
  if (i == j) return;
  if (dsu[i] > dsu[j])
    dsu[i] = j;
  else {
    if (dsu[i] == dsu[j]) dsu[i]--;
    dsu[j] = i;
  }
}
int join_(int i, int j, int c) {
  join(i << 1 | 0, (j << 1 | 0) ^ c);
  join(i << 1 | 1, (j << 1 | 1) ^ c);
  return find(i << 1 | 0) != find(i << 1 | 1);
}
int main() {
  static int p2[1000 + 1];
  static char cc[1000 + 1];
  int n, m, i, j, ans;
  scanf("%s", cc), n = strlen(cc);
  p2[0] = 1;
  for (i = 1; i <= n; i++) p2[i] = p2[i - 1] * 2 % 998244353;
  ans = 0;
  for (m = 1; m < n; m++) {
    int good, k;
    memset(dsu, -1, n * 4 * sizeof *dsu);
    good = 1;
    for (i = 0; i < n; i++)
      if (cc[i] != '?')
        if (!join_(i, n + i, cc[i] - '0')) {
          good = 0;
          break;
        }
    for (i = 0, j = n - 1; i < j; i++, j--)
      if (!join_(i, j, 0)) {
        good = 0;
        break;
      }
    for (i = m, j = n - 1; i < j; i++, j--)
      if (!join_(n + i, n + j, 0)) {
        good = 0;
        break;
      }
    memset(marked, 0, n * 4 * sizeof *marked);
    marked[find(0 << 1 | 1)] = 1;
    for (i = 0; i < m; i++) marked[find(n + i << 1 | 0)] = 1;
    marked[find(n + m << 1 | 1)] = 1;
    for (i = 0; i < n * 2; i++)
      if (marked[find(i << 1)] && marked[find(i << 1 | 1)]) {
        good = 0;
        break;
      }
    if (!good) continue;
    k = 0;
    for (i = 0; i < n * 4; i++)
      if (dsu[i] < 0) k++;
    k /= 2;
    for (i = 0; i < n * 4; i++)
      if (dsu[i] < 0 && marked[i]) k--;
    ans = (ans + p2[k]) % 998244353;
  }
  printf("%d\n", ans);
  return 0;
}