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 ase[2002], cor[2002], str[2002], ln;
int vis[2002], en[2002], en2[2002], n, dp3[2002][2];
int nexto[2002];
int dp_func3(int v, int ki) {
  if (v <= n) {
    if ((n - v + 1) > ln && (str[v] != ki && str[v] != 2)) return 0;
  }
  if (v == 1 && ki == 0) return 0;
  if (v == n + 1 && ki == 0) return 0;
  if (nexto[v] == 0) return 1;
  if (dp3[v][ki] != -1) return dp3[v][ki];
  long long ret = 0;
  if (nexto[v] == cor[v]) {
    ret += dp_func3(nexto[v], ki);
  } else {
    int p = str[v];
    if (p == 2 || (1 ^ ki) == p) ret += dp_func3(ase[v], 1);
    if (p == 2 || (0 ^ ki) == p) ret += dp_func3(ase[v], 0);
  }
  return dp3[v][ki] = ret % 998244353;
}
void dfs(int v) {
  nexto[v] = 0;
  vis[v] = 1;
  if (cor[v] && vis[cor[v]] == 0) {
    nexto[v] = cor[v];
    dfs(cor[v]);
    return;
  }
  if (ase[v] && vis[ase[v]] == 0) {
    nexto[v] = ase[v];
    dfs(ase[v]);
  }
}
int func(int l) {
  ln = l;
  int c = n;
  memset(en2, 0, sizeof en2);
  memset(vis, 0, sizeof vis);
  int diff = n - ln;
  for (int i = 1; i <= n + ln; i++) {
    ase[i] = 0;
    nexto[i] = 0;
  }
  for (int i = 1, j = ln; i <= j; i++, j--) {
    int f = ++c;
    int g = c;
    if (i != j) g++;
    if (i != j) c++;
    cor[f] = g;
    cor[g] = f;
    ase[i + diff] = g;
    ase[j + diff] = f;
    en2[f] = 1;
    ase[f] = j + diff;
    ase[g] = i + diff;
    str[g] = str[i + diff];
    str[f] = str[j + diff];
  }
  long long mul = 1;
  memset(dp3, -1, sizeof dp3);
  for (int i = 1; i <= n; i++) {
    if (vis[i]) continue;
    dfs(i);
    int p = str[i];
    long long ret = 0;
    if (p == 1 || p == 2) ret += dp_func3(i, 1);
    if (p == 0 || p == 2) ret += dp_func3(i, 0);
    ret %= 998244353;
    mul = (mul * ret) % 998244353;
  }
  for (int i = 1; i <= n; i++) {
    assert(vis[i]);
  }
  return mul;
}
int main() {
  char s[2000];
  int i, j, k, l, m;
  n = 0;
  scanf("%s", s);
  for (int i = 0; s[i]; i++) {
    if (s[i] == '?')
      str[i + 1] = 2;
    else
      str[i + 1] = s[i] - 48;
    n++;
  }
  for (int i = 1, j = n; i <= j; i++, j--) {
    cor[i] = j;
    cor[j] = i;
    en[j] = 1;
  }
  long long ans = 0;
  for (int i = 1; i <= n - 1; i++) {
    ans += func(i);
  }
  ans %= 998244353;
  cout << ans << endl;
}