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;
inline void read(int &x) {
  int v = 0, f = 1;
  char c = getchar();
  while (!isdigit(c) && c != '-') c = getchar();
  if (c == '-')
    f = -1;
  else
    v = v * 10 + c - '0';
  while (isdigit(c = getchar())) v = v * 10 + c - '0';
  x = v * f;
}
inline void read(long long &x) {
  long long v = 0ll, f = 1ll;
  char c = getchar();
  while (!isdigit(c) && c != '-') c = getchar();
  if (c == '-')
    f = -1;
  else
    v = v * 10 + c - '0';
  while (isdigit(c = getchar())) v = v * 10 + c - '0';
  x = v * f;
}
inline void readc(char &x) {
  char c;
  while ((c = getchar()) == ' ')
    ;
  x = c;
}
inline void writes(string s) { puts(s.c_str()); }
inline void writeln() { writes(""); }
inline void writei(int x) {
  if (x < 0) {
    putchar('-');
    x = abs(x);
  }
  if (!x) putchar('0');
  char a[25];
  int top = 0;
  while (x) {
    a[++top] = (x % 10) + '0';
    x /= 10;
  }
  while (top) {
    putchar(a[top]);
    top--;
  }
}
inline void writell(long long x) {
  if (x < 0) {
    putchar('-');
    x = abs(x);
  }
  if (!x) putchar('0');
  char a[25];
  int top = 0;
  while (x) {
    a[++top] = (x % 10) + '0';
    x /= 10;
  }
  while (top) {
    putchar(a[top]);
    top--;
  }
}
long long n, m, i, j, ans, vis[1005], ti, f[1005][2][2], g[2][2],
    mod = 998244353;
string st;
vector<long long> e[1005];
void dfs(long long x, long long fa) {
  vis[x] = 1;
  long long a, b, c, d;
  for ((a) = (0); (a) <= (1); (a)++)
    for ((b) = (0); (b) <= (1); (b)++)
      f[x][a][b] = (st[x] == '?' || (a ^ b ^ '0') == st[x]);
  if (x > m) f[x][0][1] = f[x][1][1] = 0;
  if (x == m) f[x][0][0] = f[x][1][0] = 0;
  for (__typeof((e[x]).begin()) it = (e[x]).begin(); it != (e[x]).end(); it++)
    if (*it != fa) {
      dfs(*it, x);
      memset(g, 0, sizeof(g));
      for ((a) = (0); (a) <= (1); (a)++)
        for ((b) = (0); (b) <= (1); (b)++)
          if (f[x][a][b])
            for ((c) = (0); (c) <= (1); (c)++)
              for ((d) = (0); (d) <= (1); (d)++)
                if (f[*it][c][d]) {
                  if (x + *it == n + 1 && a != c) continue;
                  if (x + *it == m + 1 && b != d) continue;
                  (g[a][b] += f[x][a][b] * f[*it][c][d]) %= mod;
                }
      memcpy(f[x], g, sizeof(g));
    }
}
long long solve(long long x) {
  long long ans = 1, i, j;
  memset((vis), (0), (sizeof((vis))));
  for (((i)) = (1); ((i)) <= ((n)); ((i))++) e[i].clear();
  for (((i)) = (1); ((i)) <= ((n)); ((i))++) {
    j = n + 1 - i;
    if (1 <= j && j <= n && i != j) {
      e[i].push_back(j);
      e[j].push_back(i);
    }
    j = m + 1 - i;
    if (1 <= j && j <= n && i != j) {
      e[i].push_back(j);
      e[j].push_back(i);
    }
  }
  for (((i)) = (1); ((i)) <= ((n)); ((i))++) {
    sort((e[i]).begin(), (e[i]).end());
    e[i].resize(unique((e[i]).begin(), (e[i]).end()) - e[i].begin());
  }
  for (((i)) = (1); ((i)) <= ((n)); ((i))++)
    if (!vis[i]) {
      dfs(i, 0);
      (ans *= (f[i][0][0] + f[i][0][1] + f[i][1][0] + f[i][1][1])) %= mod;
    }
  return ans;
}
int main() {
  cin >> st;
  n = st.length();
  reverse(st.begin(), st.end());
  st = " " + st;
  for (((i)) = (1); ((i)) <= ((n - 1)); ((i))++) {
    m = i;
    (ans += solve(i)) %= mod;
  }
  cout << ans << endl;
  return 0;
}