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;
int n, m;
char ch[110901];
vector<int> f[110901], ff[110901];
int col[110901];
long long Ans;
void ADD(int x, int y, int z) {
  f[x].push_back(y);
  ff[x].push_back(z);
  f[y].push_back(x);
  ff[y].push_back(z);
}
bool DFS(int x) {
  int X, tp;
  for (int i = 0; i < f[x].size(); i++) {
    X = f[x][i];
    tp = ff[x][i];
    if (tp == 0) {
      if (col[X] == -1) {
        col[X] = col[x];
        if (!DFS(X)) return false;
      }
      if (col[X] != col[x]) return false;
    } else {
      if (col[X] == -1) {
        col[X] = col[x] ^ 1;
        if (!DFS(X)) return false;
      }
      if (col[X] != (col[x] ^ 1)) return false;
    }
  }
  return true;
}
int main() {
  scanf("%s", ch + 1);
  n = strlen(ch + 1);
  for (int i = 1; i <= n / 2; i++) swap(ch[i], ch[n - i + 1]);
  if (ch[1] == '1') return printf("0"), 0;
  ch[1] = '0';
  for (m = n - 1; m; m--) {
    for (int i = 1; i <= n + m; i++) ff[i].clear(), f[i].clear(), col[i] = -1;
    for (int i = 1; i <= n / 2; i++) ADD(i, n - i + 1, 0);
    for (int i = 1; i <= m / 2; i++) ADD(n + i, n + m - i + 1, 0);
    for (int i = 1; i <= m; i++) {
      if (ch[i] == '?') continue;
      ADD(i, i + n, ch[i] - '0');
    }
    bool flag = true;
    for (int i = n; i > m; i--)
      if (ch[i] != '?') {
        if (col[i] == -1) {
          col[i] = ch[i] - '0';
          if (!DFS(i)) flag = false;
        }
        if (col[i] != ch[i] - '0') flag = false;
        if (!flag) break;
      }
    if (!flag) continue;
    long long Now = 1;
    for (int i = 1; i <= n + m; i++)
      if (col[i] == -1) {
        col[i] = 1;
        if (!DFS(i)) flag = false;
        if (!flag) break;
        Now = Now * 2 % 998244353;
      }
    if (!flag) continue;
    Ans = (Ans + Now) % 998244353;
  }
  printf("%I64d\n", Ans);
  return 0;
}