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;
char getc() {
  char c = getchar();
  while ((c < 'A' || c > 'Z') && (c < 'a' || c > 'z') && (c < '0' || c > '9'))
    c = getchar();
  return c;
}
int gcd(int n, int m) { return m == 0 ? n : gcd(m, n % m); }
int read() {
  int x = 0, f = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9')
    x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
  return x * f;
}
char s[4010];
int n, t, T, fa[4010], a[4010], p[4010], color[4010];
bool flag;
long long ans;
struct data {
  int x, y;
} e[4010];
struct data2 {
  int to, nxt;
} edge[4010];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void merge(int x, int y) { fa[find(x)] = find(y); }
int ksm(int a, int k) {
  int s = 1;
  for (; k; k >>= 1, a = 1ll * a * a % 998244353)
    if (k & 1) s = 1ll * s * a % 998244353;
  return s;
}
void addedge(int x, int y) {
  T++;
  edge[T].to = y, edge[T].nxt = p[x], p[x] = T;
}
void paint(int k, int c) {
  color[k] = c;
  for (int i = p[k]; i; i = edge[i].nxt)
    if (color[edge[i].to] == -1)
      paint(edge[i].to, c ^ 1);
    else if (color[edge[i].to] == c)
      flag = 0;
}
signed main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  reverse(s + 1, s + n + 1);
  for (int m = n - 1; m >= 1; m--) {
    for (int i = 1; i <= n + m + 2; i++) fa[i] = i;
    t = 0;
    T = 0;
    for (int i = 1; i <= n; i++) merge((i), (n - i + 1));
    for (int i = 1; i <= m; i++) merge((n + (i)), (n + (m - i + 1)));
    for (int i = n; i > m; i--) {
      if (s[i] == '0') merge((i), (n + m + 1));
      if (s[i] == '1') merge((i), (n + m + 2));
    }
    merge((n + (m)), (n + m + 2));
    for (int i = m; i >= 1; i--) {
      if (s[i] == '0') merge((i), (n + (i)));
      if (s[i] == '1') t++, e[t].x = (i), e[t].y = (n + (i));
    }
    memset(p, 0, sizeof(p));
    for (int i = 1; i <= t; i++) {
      addedge(find(e[i].x), find(e[i].y));
      addedge(find(e[i].y), find(e[i].x));
    }
    memset(color, 255, sizeof(color));
    flag = 1;
    for (int i = 1; i <= n + m + 2; i++)
      if (color[i] == -1) paint(i, 0);
    if (!flag) continue;
    int u = color[find((n + m + 1))], v = color[find((n + m + 2))];
    for (int i = 1; i <= t; i++) merge(e[i].x, e[i].y);
    if (find((n + m + 1)) == find((n + m + 2)) && u == v) continue;
    int cnt = 0;
    for (int i = 1; i <= n + m + 2; i++)
      if (find(i) == i) cnt++;
    cnt--;
    if (find((n + m + 1)) != find((n + m + 2))) cnt--;
    ans = (ans + ksm(2, cnt)) % 998244353;
  }
  cout << ans;
}