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;
using ll = long long;
char s[1024];
char a[1024];
char b[1024];
bool vis[1024];
int qcnt[1024];
int alen, blen;
ll cnt;
ll modulo = 998244353ll;
bool fill(int i) {
  if (b[i] == '?') b[i] = b[blen - 1 - i];
  if (i >= blen - alen and a[i] == '?') a[i] = a[2 * blen - 1 - i - alen];
  if (s[i] != '?' and a[i] != '?' and b[i] != '?')
    if ((s[i] - '0') xor (a[i] - '0') xor (b[i] - '0')) return false;
  if (s[i] != '?' and a[i] == '?' and b[i] != '?')
    a[i] = (s[i] - '0') xor (b[i] - '0') + '0';
  if (s[i] != '?' and a[i] != '?' and b[i] == '?')
    b[i] = (s[i] - '0') xor (a[i] - '0') + '0';
  if (b[i] != '?' and b[blen - 1 - i] != '?' and b[i] != b[blen - 1 - i])
    return false;
  if (i >= blen - alen and a[i] != '?' and a[2 * blen - 1 - i - alen] != '?' and
      a[i] != a[2 * blen - 1 - i - alen])
    return false;
  return true;
}
bool filling(int i) {
  if (not fill(i)) return false;
  if (not vis[blen - 1 - i]) {
    vis[blen - 1 - i] = true;
    if (not filling(blen - 1 - i)) return false;
  }
  if (i >= blen - alen and not vis[2 * blen - 1 - i - alen]) {
    vis[2 * blen - 1 - i - alen] = true;
    if (not filling(2 * blen - 1 - i - alen)) return false;
  }
  if (not fill(i)) return false;
  return true;
}
void counting(int i) {
  if (s[i] != '?' and a[i] != '?' and b[i] == '?') b[i] = '2';
  if (s[i] != '?' and a[i] == '?' and b[i] != '?') a[i] = '2';
  if (b[blen - 1 - i] == '?' and b[i] != '?') {
    b[blen - 1 - i] = '2';
    counting(blen - 1 - i);
  }
  if (i >= blen - alen and a[2 * blen - 1 - i - alen] == '?' and a[i] != '?') {
    a[2 * blen - 1 - i - alen] = '2';
    counting(2 * blen - 1 - i - alen);
  }
}
int main() {
  scanf("%s", s);
  int slen = strlen(s);
  ll sol = 0;
  for (alen = 1; alen < slen; alen++) {
    memset(vis, 0, sizeof(vis));
    blen = slen;
    for (int i = 0; i < blen; i++) a[i] = '?';
    for (int i = 0; i < blen; i++) b[i] = '?';
    b[0] = b[blen - 1] = '1';
    a[blen - alen] = a[blen - 1] = '1';
    for (int i = 0; i < blen - alen; i++) a[i] = '0';
    bool can = true;
    for (int i = 0; i < blen; i++) {
      if (not vis[i]) {
        if (not filling(i)) {
          can = false;
          break;
        }
      }
    }
    cnt = can;
    memset(vis, 0, sizeof(vis));
    for (int i = 0; i < blen; i++) {
      if (a[i] == '?') {
        a[i] = '2';
        counting(i);
        cnt = (cnt << 1) % modulo;
      }
      if (b[i] == '?') {
        b[i] = '2';
        counting(i);
        cnt = (cnt << 1) % modulo;
      }
    }
    sol = (sol + cnt) % modulo;
  }
  printf("%lld\n", sol);
}