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;
int n, flag, tot, ans, dis[2100], v[2100], f[2100], u[2100];
char s[2100];
vector<int> g[2100];
int odd(int x) {
  if (x & 1)
    return 1;
  else
    return 0;
}
int find(int x) {
  if (!f[x]) return x;
  f[x] = find(f[x]);
  return f[x];
}
void color(int x, int k) {
  int rt = find(x);
  if (v[rt] >= 0 && v[rt] != k)
    flag = 0;
  else
    v[rt] = k;
}
void merge(int x, int y) {
  int fx = find(x), fy = find(y);
  if (fx == fy) return;
  f[fx] = fy;
}
void link(int x, int y) {
  int fx = find(x), fy = find(y);
  if (fx == fy)
    flag = 0;
  else {
    g[fx].push_back(fy);
    g[fy].push_back(fx);
  }
}
int bfs(int s, int &num) {
  queue<int> q;
  vector<int> h[2];
  q.push(s);
  dis[s] = 0;
  u[s] = 1;
  while (q.size()) {
    int x = q.front();
    q.pop();
    if (v[x] == 0) h[0].push_back(x);
    if (v[x] == 1) h[1].push_back(x);
    for (auto t : g[x]) {
      if (u[t] && u[t] + u[x] != 0) return 0;
      if (!u[t]) {
        dis[t] = dis[x] + 1;
        u[t] = -u[x];
        q.push(t);
      }
    }
  }
  for (int i = 1; i < h[0].size(); i++) {
    if (odd(dis[h[0][i]]) != odd(dis[h[0][0]])) return 0;
  }
  for (int i = 1; i < h[1].size(); i++) {
    if (odd(dis[h[1][i]]) != odd(dis[h[1][0]])) return 0;
  }
  if (h[0].size() && h[1].size())
    if (odd(dis[h[0][0]]) + odd(dis[h[1][0]]) != 1) return 0;
  if (!h[0].size() && !h[1].size()) num = 1ll * num * 2 % 998244353;
  return 1;
}
void work() {
  int num = 1;
  queue<int> q;
  for (int i = 1; i <= tot; i++) {
    if (f[i]) continue;
    if (u[i] != 0) continue;
    if (!bfs(i, num)) return;
  }
  ans = (ans + 1ll * num) % 998244353;
}
void init(int k) {
  memset(v, -1, sizeof(v));
  memset(u, 0, sizeof(u));
  memset(f, 0, sizeof(f));
  flag = 1;
  tot = 2 * n - (k - 1);
  for (int i = 1; i <= tot; i++) g[i].clear();
}
int main() {
  cin >> s + 1;
  n = strlen(s + 1);
  for (int i = 2; i <= n; i++) {
    init(i);
    for (int j = 1; j <= n / 2; j++) {
      merge(j, n - j + 1);
    }
    int l = n - i + 1;
    for (int j = 1; j <= l / 2; j++) {
      merge(n + j, n + l - j + 1);
    }
    for (int j = i; j <= n; j++) {
      if (s[j] == '0') merge(l + j, j);
    }
    for (int j = i; j <= n; j++) {
      if (s[j] == '1') link(l + j, j);
    }
    for (int j = 1; j < i; j++) {
      if (s[j] == '1')
        color(j, 1);
      else if (s[j] == '0')
        color(j, 0);
    }
    color(n + 1, 1);
    if (flag) {
      work();
    }
  }
  cout << ans;
  return 0;
}