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, flag, cnt, res, i, p;
char str[2010];
int C[2010];
vector<pair<int, int>> V[2 * 2010];
void dfs(int i) {
  int j, sz, k, e;
  sz = V[i].size();
  for (j = 0; j < sz; j++) {
    k = V[i][j].first;
    e = V[i][j].second;
    if (C[k] == -1) {
      if (e == 0)
        C[k] = C[i];
      else
        C[k] = 1 - C[i];
      dfs(k);
    } else if ((e == 0 && C[i] != C[k]) || (e == 1 && C[i] == C[k]))
      flag = 1;
  }
}
int main() {
  scanf("%s", str);
  n = strlen(str);
  reverse(str, str + n);
  for (m = 1; m < n; m++) {
    for (i = 0; i < n + m + 2; i++) V[i].clear();
    V[n + m].push_back(make_pair(n + m + 1, 1));
    V[n + m + 1].push_back(make_pair(n + m, 1));
    for (i = 0; i < n - 1 - i; i++) {
      V[i].push_back(make_pair(n - 1 - i, 0));
      V[n - 1 - i].push_back(make_pair(i, 0));
    }
    V[n + m - 1].push_back(make_pair(n + m + 1, 0));
    V[n + m + 1].push_back(make_pair(n + m - 1, 0));
    for (i = 0; i < m - 1 - i; i++) {
      V[n + i].push_back(make_pair(n + m - 1 - i, 0));
      V[n + m - 1 - i].push_back(make_pair(n + i, 0));
    }
    for (i = 0; i < m; i++)
      if (str[i] == '1') {
        V[i].push_back(make_pair(n + i, 1));
        V[n + i].push_back(make_pair(i, 1));
      } else if (str[i] == '0') {
        V[i].push_back(make_pair(n + i, 0));
        V[n + i].push_back(make_pair(i, 0));
      }
    for (i = m; i < n; i++)
      if (str[i] == '1') {
        V[i].push_back(make_pair(n + m + 1, 0));
        V[n + m + 1].push_back(make_pair(i, 0));
      } else if (str[i] == '0') {
        V[i].push_back(make_pair(n + m, 0));
        V[n + m].push_back(make_pair(i, 0));
      }
    flag = 0;
    cnt = 0;
    memset(C, -1, sizeof C);
    for (i = 0; i < n + m + 2; i++)
      if (C[i] == -1) {
        C[i] = 0;
        dfs(i);
        cnt++;
      }
    if (!flag) {
      p = 1;
      for (i = 0; i + 1 < cnt; i++) p = 2 * p % 998244353;
      res = (res + p) % 998244353;
    }
  }
  printf("%d\n", res);
  return 0;
}