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>
char S[1212];
long long a[1212], ck[1212];
int main() {
  long long n, i, j, p, q;
  scanf("%s", S);
  for (n = 0; S[n]; n++)
    ;
  if (S[n - 1] == '1') {
    printf("0");
    return 0;
  }
  S[n - 1] = '0';
  for (i = 0; i < n; i++) {
    if (S[i] == '?')
      a[i] = 3;
    else
      a[i] = 1 << (S[i] - '0');
  }
  long long ans = 0, mod = 998244353;
  for (long long len = 1; len < n; len++) {
    long long res = 1;
    for (i = 0; i < n; i++) {
      if (ck[i]) continue;
      ck[i] = 1;
      long long now[2][2] = {!!(a[i] & 1), !!(a[i] & 2)}, flag = 0, w = i,
                bef = -1;
      while (1) {
        bef = w;
        if (!flag)
          w = n - w - 1;
        else {
          if (w < n - len) break;
          w = (len - 1) - (w - (n - len)) + (n - len);
        }
        if (w == bef) break;
        ck[w] = 1;
        flag = !flag;
        now[flag][0] = (((a[w] & 1) ? now[!flag][0] : 0) +
                        ((a[w] & 2) ? now[!flag][1] : 0)) %
                       mod;
        now[flag][1] = (((a[w] & 1) ? now[!flag][1] : 0) +
                        ((a[w] & 2) ? now[!flag][0] : 0)) %
                       mod;
        if (flag && w < n - len) now[flag][1] = 0;
      }
      res = (res * (now[flag][0] + now[flag][1])) % mod;
    }
    for (i = 0; i < n; i++) ck[i] = 0;
    ans += res;
    ans %= mod;
  }
  printf("%lld", ans);
  return 0;
}