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 double PI = acos(-1.0);
vector<long long> adjlist[2005][2];
vector<pair<pair<long long, long long>, long long> > edg;
long long vis[2005], c[2005];
string s;
long long n;
long long expo(long long base, long long exponent) {
  long long ans = 1;
  while (exponent != 0) {
    if (exponent & 1) ans = (1LL * ans * base) % 998244353;
    base = (1LL * base * base) % 998244353;
    exponent >>= 1;
  }
  return ans % 998244353;
}
void addEdge(long long u, long long v, long long w) {
  adjlist[u][w].push_back(v);
  adjlist[v][w].push_back(u);
  edg.push_back(make_pair(make_pair(u, v), w));
}
void dfs(long long node, long long color) {
  vis[node] = 1;
  c[node] = color;
  for (auto i : adjlist[node][0]) {
    if (!vis[i]) {
      dfs(i, color);
    }
  }
  for (auto i : adjlist[node][1]) {
    if (!vis[i]) {
      dfs(i, color ^ 1);
    }
  }
}
long long ans(long long k) {
  memset(c, 0, sizeof c);
  memset(vis, 0, sizeof vis);
  edg.clear();
  for (long long i = 0; i < 2005; ++i) {
    for (long long j = 0; j < 2; ++j) {
      adjlist[i][j].clear();
    }
  }
  addEdge(n + k, n + k + 1, 1);
  for (long long i = k; i < n; ++i) {
    if (s[i] != '?') {
      addEdge(n + k + s[i] - '0', i, 0);
    }
  }
  addEdge(n + k - 1, n + k + 1, 0);
  for (long long i = 0; i < k; ++i) {
    if (s[i] != '?') {
      addEdge(i, i + n, s[i] - '0');
    }
  }
  for (long long i = 0; i < n / 2; ++i) {
    addEdge(i, n - i - 1, 0);
  }
  for (long long i = 0; i < k / 2; ++i) {
    addEdge(i + n, k - i - 1 + n, 0);
  }
  long long cc = 0;
  for (long long i = 0; i < n + k + 2; ++i) {
    if (!vis[i]) {
      dfs(i, 0);
      ++cc;
    }
  }
  for (auto i : edg) {
    long long u = i.first.first;
    long long v = i.first.second;
    long long w = i.second;
    if (c[u] ^ c[v] != w) {
      return 0;
    }
  }
  return expo(2, cc - 1);
}
void solve() {
  cin >> s;
  n = (long long)s.size();
  reverse(s.begin(), s.end());
  long long ret = 0;
  for (long long i = 1; i < n; ++i) {
    ret += ans(i);
    if (ret >= 998244353) ret -= 998244353;
  }
  cout << ret << '\n';
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long t = 1;
  while (t--) {
    solve();
  }
  return 0;
}