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 maxn = 1e3, maxnodes = 2 * maxn + 7, mod = 998244353;
vector<int> adjlist[2][maxnodes];
int color[maxnodes], slength, vis[maxnodes];
long long ans = 0;
string s;
long long power(long long a, long long b, long long m) {
  if (b == 0) return 1;
  long long tmp = power(a, b / 2, m);
  tmp = (tmp * tmp) % m;
  if (b & 1) tmp = (tmp * a) % m;
  return tmp;
}
long long add(long long a, long long b, long long m) { return (a + b) % m; }
void clear() {
  for (int i = 0; i < maxnodes; i++) {
    color[i] = -1;
    vis[i] = 0;
    adjlist[0][i].clear();
    adjlist[1][i].clear();
  }
}
bool is_bipartite(int cur, int eval) {
  if (color[cur] == -1) color[cur] = eval;
  if (color[cur] != eval) return false;
  if (vis[cur]) return true;
  vis[cur] = 1;
  for (int i = 0; i < 2; i++) {
    for (auto u : adjlist[i][cur]) {
      if (is_bipartite(u, color[cur] ^ i)) continue;
      return false;
    }
  }
  return true;
}
long long solve(int lendiff) {
  int alen = slength - lendiff, components = 0;
  for (int i = 1; i <= (slength / 2); i++) {
    adjlist[0][i].push_back(slength - i + 1);
    adjlist[0][slength - i + 1].push_back(i);
  }
  for (int i = 1; i <= (alen / 2); i++) {
    adjlist[0][i + slength].push_back(alen - i + 1 + slength);
    adjlist[0][alen - i + 1 + slength].push_back(i + slength);
  }
  color[slength + alen + 1] = 1;
  color[slength + alen + 2] = 0;
  color[slength + 1] = 1;
  color[1] = 1;
  adjlist[1][slength + alen + 1].push_back(slength + alen + 2);
  adjlist[1][slength + alen + 2].push_back(slength + alen + 1);
  adjlist[0][slength + alen + 1].push_back(1);
  adjlist[0][1].push_back(slength + alen + 1);
  adjlist[0][slength + alen + 1].push_back(slength + 1);
  adjlist[0][slength + 1].push_back(slength + alen + 1);
  for (int i = 0; i < slength; i++) {
    if (i < lendiff) {
      if (s[i] == '1') {
        adjlist[0][slength + alen + 1].push_back(i + 1);
        adjlist[0][i + 1].push_back(slength + alen + 1);
      } else if (s[i] == '0') {
        adjlist[0][slength + alen + 2].push_back(i + 1);
        adjlist[0][i + 1].push_back(slength + alen + 2);
      }
    } else {
      if (s[i] == '?') continue;
      int pos1 = i + 1, pos2 = slength + i - lendiff + 1, parity = s[i] - '0';
      adjlist[parity][pos1].push_back(pos2);
      adjlist[parity][pos2].push_back(pos1);
    }
  }
  for (int i = slength + alen + 2; i >= 1; i--) {
    if (vis[i]) continue;
    if (is_bipartite(i, 0))
      components++;
    else
      return 0;
  }
  return power(2, components - 1, mod);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ;
  cin >> s;
  slength = s.size();
  for (int i = 0; i < s.size(); i++) {
    clear();
    ans = add(ans, solve(i), mod);
  }
  cout << ans;
  return 0;
}