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 p = 998244353;
long long pow_mod(long long x, long long n) {
  long long s = 1;
  for (; n; n >>= 1) {
    if (n & 1) s = s * x % p;
    x = x * x % p;
  }
  return s;
}
int n, O;
char s[1010];
struct Edge {
  int to, next, w;
} e[2010 * 8];
int c1, head[2010];
inline void add_edge(int u, int v, int w) {
  e[c1].to = v;
  e[c1].w = w;
  e[c1].next = head[u];
  head[u] = c1++;
}
inline void Add_edge(int u, int v, int w) {
  add_edge(u, v, w);
  add_edge(v, u, w);
}
int col[2010];
bool F;
void dfs(int u, int c) {
  col[u] = c;
  for (int i = head[u]; ~i; i = e[i].next) {
    int v = e[i].to, w = e[i].w;
    if (col[v]) {
      if (col[v] != (w ? -c : c)) F = 0;
      continue;
    }
    dfs(v, w ? -c : c);
  }
}
long long ans;
int main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  O = 2 * n + 1;
  reverse(s + 1, s + n + 1);
  for (int l = 1; l < n; ++l) {
    memset(head, -1, sizeof head);
    c1 = 0;
    memset(col, 0, sizeof col);
    Add_edge(1, O, 1);
    for (int i = 1; i <= l; ++i) Add_edge(i, l - i + 1, 0);
    for (int i = 1; i <= n; ++i) Add_edge(n + i, n + n - i + 1, 0);
    for (int i = 1; i <= n; ++i) {
      if (s[i] == '?') continue;
      int v = s[i] - '0';
      if (i > l)
        Add_edge(i + n, O, v);
      else
        Add_edge(i, i + n, v);
    }
    int s = 0;
    F = 1;
    for (int i = 1; i <= l; ++i)
      if (!col[i]) dfs(i, 1), ++s;
    for (int i = 1; i <= n; ++i)
      if (!col[i + n]) dfs(i + n, 1), ++s;
    if (F) ans = (ans + pow_mod(2, s - 1)) % p;
  }
  cout << ans << endl;
  return 0;
}