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>
const int MAXN = 1010, M = 998244353;
int Pow(int x, int k) {
  int ret = 1;
  for (; k; x = 1ll * x * x % M, k >>= 1)
    if (k & 1) ret = 1ll * ret * x % M;
  return ret;
}
int first[MAXN << 1], tote;
struct edge {
  int to, net;
} e[MAXN << 2];
inline void addedge(const int &u, const int &v) {
  ++tote;
  e[tote].to = v, e[tote].net = first[u], first[u] = tote;
  ++tote;
  e[tote].to = u, e[tote].net = first[v], first[v] = tote;
}
inline void ClearMap() {
  tote = 0;
  memset(first, 0, sizeof(first));
}
int fa[MAXN << 1];
void BuildDisjointSet(const int &n) {
  for (int i = 1; i <= n; ++i) fa[i] = i;
}
int get(const int &x) { return (fa[x] == x) ? x : fa[x] = get(fa[x]); }
inline void merge(int x, int y) {
  x = get(x), y = get(y);
  fa[y] = x;
}
bool vis[MAXN << 1], color[MAXN << 1];
inline void ClearDfs() { memset(vis, 0, sizeof(vis)); }
bool dfs(const int &u) {
  vis[u] = 1;
  for (int l = first[u]; l; l = e[l].net) {
    int v = e[l].to;
    if (v == u)
      return 0;
    else {
      if (!vis[v]) {
        color[v] = !color[u];
        if (!dfs(v)) return 0;
      } else {
        if (color[v] != !color[u]) return 0;
      }
    }
  }
  return 1;
}
char s[MAXN];
int work(const int &m, const int &len) {
  ClearMap();
  BuildDisjointSet(m * 2);
  ClearDfs();
  for (int i = 2; i <= m - len; ++i) {
    if (s[i - 1] == '0')
      merge(i, (m + 1));
    else if (s[i - 1] == '1')
      merge(i, 1);
    merge(m + i, (m + 1));
  }
  merge(m + m - len + 1, 1);
  for (int i = m - len + 1; i <= m; ++i)
    if (s[i - 1] == '0') merge(i, m + i);
  for (int i = 1, j = m; i < j; ++i, --j) merge(i, j);
  for (int i = m - len + 1, j = m; i < j; ++i, --j) merge(m + i, m + j);
  for (int i = m - len + 1; i <= m; ++i)
    if (s[i - 1] == '1') addedge(get(i), get(m + i));
  addedge(get((m + 1)), get(1));
  int ret = 0;
  for (int i = 1; i <= m * 2; ++i)
    if (!vis[get(i)]) {
      if (dfs(get(i)) == 0)
        return 0;
      else
        ++ret;
    }
  return Pow(2, ret - 1);
}
int main() {
  scanf("%s", s);
  int m = 0;
  while (s[m] == '1' || s[m] == '0' || s[m] == '?') ++m;
  int ans = 0;
  for (int len = m - 1; len >= 1; --len) ans = (ans + work(m, len)) % M;
  printf("%d", ans);
}