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 iinf = 1 << 29;
const long long inf = 1ll << 60;
const long long mod = 998244353;
void GG() {
  cout << "-1\n";
  exit(0);
}
long long mpow(long long a, long long n, long long mo = mod) {
  long long re = 1;
  while (n > 0) {
    if (n & 1) re = re * a % mo;
    a = a * a % mo;
    n >>= 1;
  }
  return re;
}
long long inv(long long b, long long mo = mod) {
  if (b == 1) return b;
  return (mo - mo / b) * inv(mo % b) % mo;
}
const int maxn = 2000 + 5;
long long re = 0;
string second;
int n;
vector<int> a;
vector<pair<int, int> > g[maxn];
bool seen[maxn];
int col[maxn];
void d(int v) {
  seen[v] = 1;
  for (pair<int, int> u : g[v]) {
    if (!seen[u.first]) {
      d(u.first);
    }
  }
}
bool dfs(int v) {
  for (pair<int, int> u : g[v]) {
    if (col[u.first] == -1) {
      col[u.first] = col[v] ^ u.second;
      if (!dfs(u.first)) return 0;
    } else {
      if (col[u.first] != col[v] ^ u.second) return 0;
    }
  }
  return 1;
}
int N = 0;
void go(int len) {
  memset(col, -1, sizeof col);
  memset(seen, 0, sizeof seen);
  int M = 0;
  for (int i = 0; i < maxn; i++) g[i].clear();
  int st = n - len;
  for (int i = 0; i < n; i++) {
    g[i].push_back({n - i - 1, 0});
  }
  for (int i = st; i < n; i++) {
    g[i + n].push_back({n + st - i - 1 + n, 0});
  }
  for (int i = 0; i < n; i++) {
    if (second[i] != '?') {
      g[i].push_back({i + n, second[i] - '0'});
      g[i + n].push_back({i, second[i] - '0'});
    }
  }
  for (int i = 1; i < st; i++) {
    g[0 + n].push_back({i + n, 0});
    g[i + n].push_back({0 + n, 0});
  }
  g[0 + n].push_back({st + n, 1});
  g[st + n].push_back({0 + n, 1});
  for (int i = 0; i < n * 2; i++) {
    ;
    for (pair<int, int> u : g[i]) {
      ;
    }
  }
  int x = 0;
  for (int i = 0; i < n * 2; i++) {
    if (!seen[i]) d(i), ++x;
  }
  for (int i = 0; i < n * 2; i++) {
    if (col[i] == -1) {
      col[i] = 0;
      if (!dfs(i)) return;
    }
  };
  re += mpow(2, x);
  re %= mod;
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  ;
  cin >> second;
  n = second.length();
  for (int i = 0; i < n; i++) {
    a.push_back(min(n - i, i));
  };
  for (int i = 1; i < n; i++) {
    ;
    go(i);
  }
  cout << re * inv(2) % mod << '\n';
}