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;
long long i, i1, j, k, k1, t, n, m, res, flag[10], a[1010], b, x, ls;
string s;
bool vis[1010];
vector<long long> adj[1010];
void dfs(long long s) {
  if (vis[s]) return;
  vis[s] = true;
  ls = s;
  if (a[s] == 0 || a[s] == 1)
    x ^= a[s];
  else
    k++;
  for (auto u : adj[s]) dfs(u);
}
void init(long long m) {
  long long i, tt;
  for (i = 1; i <= n; i++) vis[i] = false;
  for (i = 1; i <= n; i++) adj[i].clear();
  for (i = 1; i <= n; i++) adj[i].push_back(n - i + 1);
  for (i = m + 1; i <= n; i++) adj[i].push_back(n - i + m + 1);
  tt = 1;
  for (i = 1; i <= n; i++) {
    if (vis[i]) continue;
    k = 0;
    x = 0;
    dfs(i);
    if (k == 0 && x == 1 && ls != i && ls <= m) tt = 0;
    if (ls != i && ls <= m) k--;
    for (j = 1; j <= k; j++) tt = (2 * tt) % 998244353;
  }
  res += tt;
  res %= 998244353;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> s;
  n = s.size();
  s = '#' + s;
  for (i = 1; i <= n; i++) a[i] = (long long)s[i] - '0';
  if (a[n] == 1) {
    cout << 0 << "\n";
    return 0;
  } else {
    a[n] = 0;
  }
  for (i = 1; i <= n - 1; i++) init(i);
  cout << res << "\n";
  return 0;
}