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;
long long po(long long x, long long y) {
  long long res = 1;
  for (; y; y >>= 1) {
    if (y & 1) res = res * x % 998244353;
    x = x * x % 998244353;
  }
  return res;
}
string s;
long long m, dece;
namespace solve {
struct edge {
  long long to;
  bool w;
};
edge edges(long long to, bool w) {
  edge gen;
  gen.to = to, gen.w = w;
  return gen;
}
vector<edge> g[2010];
void make_edge(long long a, long long b, bool w) {
  g[a].push_back(edges(b, w));
  g[b].push_back(edges(a, w));
}
long long vis[2010], n;
bool used, ok;
set<bool> st;
void dfs(long long x, bool col) {
  if (~vis[x]) {
    if (col != vis[x]) ok = 0;
    return;
  }
  vis[x] = col;
  if (x < m - n && s[m - 1 - x] != '?') {
    used = 1;
    st.insert(col ^ (s[m - 1 - x] - '0'));
  }
  if (x == m || x == m + n - 1) {
    used = 1;
    st.insert(col ^ 1);
  }
  for (auto y : g[x]) {
    dfs(y.to, col ^ y.w);
  }
}
long long main(long long nn) {
  n = nn;
  for (int i = 0; i < 2010; i++) g[i].clear();
  for (int i = n; i <= m - 1 - i; i++) {
    if (s[i] != '?' && s[m - 1 - i] != '?' && s[i] != s[m - 1 - i]) return 0;
    make_edge(i, m - 1 - i, 0);
  }
  for (long long i = 0; i < n; i++) {
    if (s[i] == '?') continue;
    long long vb = min(i, m - 1 - i);
    long long va = min(i, n - 1 - i) + m;
    make_edge(va, vb, s[i] - '0');
  }
  for (int i = 0; i < n + m; i++) vis[i] = -1;
  long long ans = 1;
  for (int i = 0; i < n + m; i++) {
    if (i >= m) {
      long long j = i - m;
      if (j > n - 1 - j) continue;
    } else if (i > m - 1 - i)
      continue;
    if (~vis[i]) continue;
    used = 0, ok = 1;
    st.clear();
    dfs(i, 0);
    if (st.size() == 2) ok = 0;
    if (ok == 0) return 0;
    if (used == 0) ans = ans * 2 % 998244353;
  }
  return ans - dece;
}
};  // namespace solve
int main() {
  cin >> s;
  reverse(s.begin(), s.end());
  m = s.size();
  long long ans = 0;
  for (int n = 1; n < m; n++) {
    ans = (ans + solve::main(n)) % 998244353;
  }
  if (ans < 0) ans += 998244353;
  cout << ans << endl;
  return 0;
}