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 long long mod = 998244353LL;
typedef struct EDGE {
  int from, to, type, vis;
  EDGE() { vis = 0; }
  EDGE(int _f, int _t, int _ty) : from(_f), to(_t), type(_ty) { vis = 0; }
} Edge;
char s[2010];
vector<Edge> edges;
vector<int> G[2010];
int n, vis[2010], tot, nodes[2010];
inline void addEdge(int from, int to, int type) {
  edges.push_back(Edge(from, to, type));
  edges.push_back(Edge(to, from, type));
  G[from].push_back(tot++);
  G[to].push_back(tot++);
}
void build(int k) {
  for (int i = 0; i <= n + k; i++) {
    G[i].clear();
    vis[i] = 0;
    nodes[i] = -1;
  }
  edges.clear();
  tot = 0;
  nodes[0] = 0;
  nodes[n + 1] = 1;
  int u, v;
  for (int i = 0; i < n; i++) {
    if (s[i] == '?') continue;
    if (i < n - k)
      addEdge(0, i + 1, s[i] - '0');
    else
      addEdge(i + 1 + k, i + 1, s[i] - '0');
  }
  u = 1;
  v = n;
  while (u < v) {
    addEdge(u, v, 0);
    u++;
    v--;
  }
  u = n + 1;
  v = n + k;
  while (u < v) {
    addEdge(u, v, 0);
    u++;
    v--;
  }
}
long long dfs(int u) {
  vis[u] = 1;
  int Gs = G[u].size();
  for (int i = 0; i < Gs; i++) {
    Edge &e = edges[G[u][i]];
    Edge &eo = edges[G[u][i] ^ 1];
    if (e.vis) continue;
    if (nodes[e.to] != -1 && nodes[e.to] ^ e.type != nodes[u]) return 0;
    nodes[e.to] = nodes[u] ^ e.type;
    e.vis = 1;
    eo.vis = 1;
    if (!dfs(e.to)) return 0;
  }
  return 1LL;
}
long long qpow(long long a, long long t) {
  long long ret = 1LL;
  while (t) {
    ret = t & 1 ? ret * a % mod : ret;
    a = a * a % mod;
    t >>= 1;
  }
  return ret;
}
void disp(int N) {
  for (int i = 0; i <= N; i++) {
    cout << i << "(" << vis[i] << ") ";
  }
  cout << endl;
}
int main() {
  while (cin >> s) {
    n = strlen(s);
    long long ans = 0;
    for (int k = 1; k < n; k++) {
      build(k);
      int cur = dfs(0) && dfs(n + 1) ? 0 : -1;
      for (int i = 0; cur >= 0 && i <= n + k; i++) {
        if (!vis[i]) {
          nodes[i] = 0;
          cur = dfs(i) ? cur + 1 : -1;
        }
      }
      ans = cur >= 0 ? (ans + qpow(2LL, cur)) % mod : ans;
    }
    cout << ans << endl;
  }
  return 0;
}