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 int64 = long long;
constexpr int64 mod = 998244353;
class Solver {
 public:
  Solver() {}
  void init(std::size_t size) {
    size_ = size;
    next_.resize(size);
    for (auto &n : next_) {
      n.clear();
    }
    values_.resize(size);
    for (auto &v : values_) {
      v = -1;
    }
  }
  explicit Solver(std::size_t size)
      : size_(size), next_(size_), values_(size_, -1) {}
  void add_equal(int a, int b) { add_constrain(a, b, true); }
  void add_different(int a, int b) { add_constrain(a, b, false); }
  void add_constrain(int a, int b, bool are_equal) {
    next_[a].push_back({b, are_equal});
    next_[b].push_back({a, are_equal});
  }
  bool add_zero(int a) { return add_number(a, 0); }
  bool add_one(int a) { return add_number(a, 1); }
  bool add_number(int a, int value) {
    if (values_[a] != -1) {
      return values_[a] == value;
    }
    values_[a] = value;
    for (auto e : next_[a]) {
      if (!add_number(e.dest, e.are_equal ? value : 1 - value)) {
        return false;
      }
    }
    return true;
  }
  bool is_fixed(int a) { return values_[a] != -1; }

 private:
  std::size_t size_;
  struct Edge {
    int dest;
    bool are_equal;
  };
  std::vector<std::vector<Edge>> next_;
  std::vector<int> values_;
};
Solver solver;
int64 solve(const std::string &mask, int a_size, int b_size) {
  solver.init(b_size * 2);
  for (int i = b_size, j = b_size + b_size - 1; i < j; i++, j--) {
    solver.add_equal(i, j);
  }
  for (int i = b_size - a_size, j = b_size - 1; i < j; i++, j--) {
    solver.add_equal(i, j);
  }
  for (int i = 0; i < b_size; i++) {
    switch (mask[i]) {
      case '0':
        solver.add_equal(i, b_size + i);
        break;
      case '1':
        solver.add_different(i, b_size + i);
        break;
      case '?':
        break;
    }
  }
  for (int i = b_size - a_size - 1; i >= 0; i--) {
    if (!solver.add_zero(i)) {
      return 0;
    }
  }
  if (!solver.add_one(b_size - a_size)) {
    return 0;
  }
  int64 res = 1;
  for (int i = 0; i < b_size * 2; i++) {
    if (solver.is_fixed(i)) {
      continue;
    }
    if (!solver.add_zero(i)) {
      return 0;
    }
    res = (res * 2) % mod;
  }
  return res;
}
int64 solve(const std::string &mask) {
  int b_size = (int)mask.size();
  int64 res = 0;
  for (int a_size = 1; a_size < b_size; a_size++) {
    res = (res + solve(mask, a_size, b_size)) % mod;
  }
  return res;
}
int main() {
  std::string mask;
  while (std::cin >> mask) {
    std::cout << solve(mask) << std::endl;
  }
}