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 inf = 0x3f3f3f3f;
const double eps = 1e-6;
const long long mod = 998244353;
inline string getstr(string &s, long long l, long long r) {
  string ret = "";
  for (long long i = l; i <= r; i++) ret.push_back(s[i]);
  return ret;
}
long long modpow(long long x, long long y, long long md = mod) {
  if (y == 0) return 1;
  long long ret = modpow(x, y >> 1, md);
  ret = (long long)ret * ret % md;
  if (y & 1) ret = (long long)ret * x % md;
  return ret;
}
string s;
vector<pair<long long, long long> > g[2005];
long long value[2005];
long long LEN = 0;
bool error = 0;
void add_edge(long long x, long long y, long long cost) {
  g[x].push_back(make_pair(y, cost));
  g[y].push_back(make_pair(x, cost));
}
void dfs(long long x) {
  if (error) return;
  for (auto p : g[x]) {
    if (~value[p.first] && value[p.first] != value[x] ^ p.second) error = 1;
    if (error) return;
    if (~value[p.first]) continue;
    value[p.first] = value[x] ^ p.second;
    dfs(p.first);
  }
}
long long calc(long long len) {
  LEN = len;
  memset(value, -1, sizeof value);
  long long Maxa = (len) / 2;
  long long Maxb = ((long long)s.size() - 1) / 2;
  swap(Maxa, Maxb);
  for (long long i = 0; i <= 2002; i++) g[i].clear();
  value[0] = 1;
  value[1001] = 1;
  for (long long i = 0; i < s.size(); i++) {
    if (s[i] == '?') continue;
    long long posa = (i <= Maxa ? i : ((long long)s.size() - i - 1));
    long long posb = (i <= Maxb ? i : (len - i));
    if (i > len) {
      if (~value[posa] && value[posa] != s[i] - '0') return 0;
      value[posa] = s[i] - '0';
      continue;
    }
    add_edge(posa, posb + 1001, s[i] - '0');
  }
  long long ret = 1;
  error = 0;
  for (long long i = 1; i <= 2002; i++) {
    if (~value[i]) dfs(i);
  }
  for (long long i = 1; i <= 2002; i++) {
    if (((0 <= i && i <= Maxa) || (1001 <= i && i <= 1001 + Maxb)) &&
        value[i] == -1) {
      value[i] = 0;
      (ret *= 2) %= mod;
      dfs(i);
    }
    if (error) return 0;
  }
  return ret;
}
signed main() {
  cin >> s;
  reverse(s.begin(), s.end());
  long long ans = 0;
  for (long long len = 0; len < s.size(); len++) {
    (ans += calc(len)) %= mod;
  }
  cout << ans << endl;
  return 0;
}