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 mod = 998244353;
int mu(int x, int y) { return 1ll * x * y % mod; }
void up(int &x, int y) {
  x += y;
  if (x >= mod) x -= mod;
}
int ans;
char ss[1005];
int n;
int col[2005];
int la[2005], owo, nt[100005], le[100005], en[100005];
void adg(int x, int y, int z) {
  en[++owo] = y;
  nt[owo] = la[x];
  la[x] = owo;
  le[owo] = z;
  en[++owo] = x;
  nt[owo] = la[y];
  la[y] = owo;
  le[owo] = z;
}
bool dfs(int x) {
  for (int it = la[x]; it; it = nt[it]) {
    int y = en[it];
    if (col[y] == -1) {
      col[y] = (col[x] ^ le[it]);
      if (!dfs(y)) return 0;
    } else if ((col[y] ^ le[it]) != col[x])
      return 0;
  }
  return 1;
}
int main() {
  scanf("%s", &ss[1]);
  n = strlen(ss + 1);
  if (ss[n] == '1') {
    puts("0");
    return 0;
  }
  ss[n] = '0';
  for (int m = n - 1; m >= 1; m--) {
    owo = 0;
    int now = 1;
    bool fl = 1;
    for (int i = 1; i <= n + m; i++) {
      la[i] = 0;
      col[i] = -1;
    }
    for (int i = 1; i <= n / 2; i++) {
      adg(i, n - i + 1, 0);
    }
    for (int i = 1; i <= m / 2; i++) {
      adg(n + i, n + m - i + 1, 0);
    }
    for (int i = 1; i <= m; i++) {
      if (ss[i] == '?') continue;
      adg(i, n + i, ss[i] - '0');
    }
    for (int i = m + 1; i <= n; i++) {
      if (ss[i] == '?') continue;
      if (col[i] == -1) {
        col[i] = ss[i] - '0';
        if (!dfs(i)) fl = 0;
      } else if (col[i] != ss[i] - '0')
        fl = 0;
      if (!fl) break;
    }
    for (int i = 1; i <= n + m; i++) {
      if (col[i] == -1) {
        col[i] = 0;
        if (!dfs(i)) fl = 0;
        now = mu(now, 2);
      }
      if (!fl) break;
    }
    if (fl) up(ans, now);
  }
  printf("%d", ans);
}