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 N = 3e5 + 5;
const long long mod = 998244353;
long long qpow(long long x, long long n) {
  long long res = 1;
  while (n) {
    if (n & 1) res = res * x % mod;
    x = x * x % mod;
    n >>= 1;
  }
  return res;
}
vector<pair<long long, int> > g[N];
int c[N], len;
char s[N];
bool dbg = 0;
bool dfs(int u) {
  if (c[u] == -1) c[u] = 1;
  for (auto it : g[u]) {
    if (c[it.first] == -1) {
      if (it.second == 0)
        c[it.first] = c[u];
      else
        c[it.first] = 1 - c[u];
      if (!dfs(it.first)) return false;
    } else if (abs(c[it.first] - c[u]) != it.second)
      return false;
  }
  return true;
}
long long solve(int x) {
  for (int i = (1); i < (len * 2 + 1); i++) g[i].clear(), c[i] = -1;
  c[len] = 1;
  g[len].push_back(pair<long long, int>(len + x, 0));
  g[len + x].push_back(pair<long long, int>(len, 0));
  for (int i = 1; i <= len; ++i)
    g[i].push_back(pair<long long, int>(len + 1 - i, 0));
  for (int i = 1; i <= x; ++i)
    g[len + i].push_back(pair<long long, int>(len + x + 1 - i, 0));
  for (int i = 1; i <= len; ++i) {
    if (s[i] != '?') {
      g[i].push_back(pair<long long, int>(len + i, s[i] - '0'));
      g[len + i].push_back(pair<long long, int>(i, s[i] - '0'));
    }
  }
  for (int i = x + 1; i < len; ++i) {
    g[i + len].push_back(pair<long long, int>(i + len + 1, 0));
    g[i + len + 1].push_back(pair<long long, int>(i + len, 0));
  }
  g[x + 1 + len].push_back(pair<long long, int>(len + x, 1));
  g[x + len].push_back(pair<long long, int>(len + x + 1, 1));
  c[x + 1 + len] = 0;
  long long cnt = 0;
  if ((!dfs(len)) || (!dfs(len + x + 1))) return 0;
  for (int i = 1; i <= len + len; ++i) {
    if (c[i] == -1) {
      if (dfs(i))
        cnt++;
      else
        return 0;
    }
  }
  long long res = qpow(2, cnt);
  return res;
}
int main() {
  cin >> s + 1;
  len = strlen(s + 1);
  reverse(s + 1, s + len + 1);
  long long ans = 0;
  for (int i = 1; i < len; ++i) {
    ans = (ans + solve(i)) % mod;
  }
  cout << ans << endl;
  return 0;
}