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 int MOD = 998244353;
const int MAXN = 1010;
int n, offset_a, offset_b, sol;
int pow2[2 * MAXN], color[2 * MAXN];
char s[MAXN];
vector<pair<int, bool>> v[2 * MAXN];
inline int add(int a, int b) {
  if (a + b < 0) return a + b + MOD;
  if (a + b >= MOD) return a + b - MOD;
  return a + b;
}
inline void init() {
  pow2[0] = 1;
  for (int i = 1; i < 2 * MAXN; ++i) pow2[i] = add(pow2[i - 1], pow2[i - 1]);
}
inline void clear() {
  memset(color, -1, sizeof color);
  for (int i = 0; i < 2 * MAXN; ++i) v[i].clear();
}
void build_graph(int a_size) {
  for (int i = 0; i < a_size; ++i) {
    if (i >= a_size - i - 1) break;
    int A = i + offset_a, B = a_size - i - 1 + offset_a;
    v[A].emplace_back(B, false);
    v[B].emplace_back(A, false);
  }
  v[a_size - 1 + offset_a].emplace_back(1, false);
  v[1].emplace_back(a_size - 1 + offset_a, false);
  for (int i = 0; i < n; ++i) {
    if (i >= n - i - 1) break;
    int A = i + offset_b, B = n - i - 1 + offset_b;
    v[A].emplace_back(B, false);
    v[B].emplace_back(A, false);
  }
  v[0].emplace_back(1, true);
  v[1].emplace_back(0, true);
  for (int i = 0; i < n; ++i) {
    char c = s[n - i - 1];
    if (c == '?') continue;
    if (i >= a_size) {
      int A = c - '0';
      int B = i + offset_b;
      v[A].emplace_back(B, false);
      v[B].emplace_back(A, false);
    } else {
      int A = i + offset_a;
      int B = i + offset_b;
      v[A].emplace_back(B, c == '1');
      v[B].emplace_back(A, c == '1');
    }
  }
}
bool dfs(int node, int col) {
  if (color[node] != -1) return color[node] == col;
  color[node] = col;
  bool ret = true;
  for (const auto &p : v[node]) ret &= dfs(p.first, col ^ p.second);
  return ret;
}
int solve(int size_a) {
  int comp_cnt = 0, ret = 0;
  bool bipartite = true;
  for (int i = 0; i < 2 + size_a + n; ++i) {
    if (color[i] != -1) continue;
    bipartite &= dfs(i, 0);
    ++comp_cnt;
  }
  if (bipartite) ret = pow2[comp_cnt - 1];
  return ret;
}
int main(void) {
  scanf("%s", s);
  n = strlen(s);
  init();
  for (int i = 1; i < n; ++i) {
    clear();
    offset_a = 2;
    offset_b = 2 + i;
    build_graph(i);
    sol = add(sol, solve(i));
  }
  printf("%d\n", sol);
  return 0;
}