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;
char s[1010];
int m, lena, starta, mirror[2][1010], memo[2][1010][2][2];
bool visited[1010];
long long f(int ar, int pos, int dir, int bit) {
  visited[pos] = true;
  if (dir == 1 and pos < starta) {
    if (s[pos] == '0') return 1 - bit;
    if (s[pos] == '1') return bit;
    return 1;
  }
  if (memo[ar][pos][dir][bit] != -1) {
    return memo[ar][pos][dir][bit];
  }
  long long ret;
  if (dir == 0) {
    if (mirror[ar][pos] == pos) {
      ret = 1;
    } else {
      ret = f(ar, mirror[ar][pos], 1, bit);
    }
  } else {
    if (s[pos] == '0') ret = f(1 - ar, pos, 0, 1 - bit);
    if (s[pos] == '1') ret = f(1 - ar, pos, 0, bit);
    if (s[pos] == '?')
      ret = (f(1 - ar, pos, 0, 0) + f(1 - ar, pos, 0, 1)) % 998244353;
  }
  return memo[ar][pos][dir][bit] = ret;
}
int main() {
  while (scanf("%s", s) > 0) {
    m = strlen(s);
    if (m == 1 or s[m - 1] == '1') {
      printf("0\n");
      continue;
    }
    for (int i = 0; i < m; i++) {
      mirror[1][i] = m - 1 - i;
    }
    long long ans = 0;
    for (lena = 1; lena < m; lena++) {
      starta = m - lena;
      for (int i = starta; i < m; i++) {
        mirror[0][i] = m - 1 - i + starta;
      }
      memset(memo, -1, sizeof memo);
      memset(visited, false, sizeof visited);
      visited[0] = visited[m - 1] = true;
      long long ways = 1;
      if (lena > 1) {
        if (s[starta] == '0') {
          ways = f(1, starta, 0, 1);
        }
        if (s[starta] == '1') {
          ways = f(1, starta, 0, 0);
        }
        if (s[starta] == '?') {
          ways = (f(1, starta, 0, 0) + f(1, starta, 0, 1)) % 998244353;
        }
      }
      for (int i = 1; i < starta; i++) {
        if (visited[i]) continue;
        if (s[i] == '0') ways = (ways * f(1, i, 0, 0)) % 998244353;
        if (s[i] == '1') ways = (ways * f(1, i, 0, 1)) % 998244353;
        if (s[i] == '?')
          ways = (ways * ((f(1, i, 0, 0) + f(1, i, 0, 1)) % 998244353)) %
                 998244353;
      }
      ans = (ans + ways) % 998244353;
    }
    printf("%lld\n", ans);
  }
}