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;
int fastMax(int x, int y) { return (((y - x) >> (32 - 1)) & (x ^ y)) ^ y; }
int fastMin(int x, int y) { return (((y - x) >> (32 - 1)) & (x ^ y)) ^ x; }
const int MAXN = 1005;
const int MOD = 998244353;
int vis[2 * MAXN];
int parity[2 * MAXN];
vector<pair<int, int>> con[2 * MAXN];
bool error;
void clear() {
  memset((vis), 0, sizeof((vis)));
  memset((parity), 0, sizeof((parity)));
  for (int i = (0); i <= (2 * MAXN - 1); ++i) con[i].clear();
  error = 0;
}
int m;
void dfs(int u) {
  vis[u] = 1;
  for (auto v : con[u]) {
    if (!vis[v.first]) {
      parity[v.first] = parity[u] ^ v.second;
      dfs(v.first);
    } else if (parity[v.first] != (parity[u] ^ v.second)) {
      error = 1;
    }
  }
}
char str[MAXN];
void solve() {
  string second;
  scanf("%s", str);
  second = (string)str;
  reverse(second.begin(), second.end());
  int n = second.length();
  int all = 0;
  for (int m = 1; m < n; m++) {
    clear();
    for (int i = 1; i < n - i + 1; i++) {
      con[i].push_back({n - i + 1, 0});
      con[n - i + 1].push_back({i, 0});
    }
    for (int i = 1; i < m - i + 1; i++) {
      con[n + i].push_back({n + m - i + 1, 0});
      con[n + m - i + 1].push_back({n + i, 0});
    }
    for (int i = 1; i <= n; i++) {
      if (second[i - 1] != '?') {
        int p = second[i - 1] - '0';
        con[i].push_back({n + i, p});
        con[n + i].push_back({i, p});
      }
    }
    for (int i = m + 1; i <= n; i++) {
      con[0].push_back({n + i, 0});
      con[n + i].push_back({0, 0});
    }
    con[n + m].push_back({0, 1});
    con[0].push_back({n + m, 1});
    int ans = 1;
    for (int i = 0; i < 2 * n; i++) {
      if (!vis[i]) {
        dfs(i);
        if (i) ans = (ans * 2) % MOD;
      }
    }
    if (error) ans = 0;
    all = (all + ans) % MOD;
  }
  cout << all << endl;
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  int t, w;
  t = 1;
  for (int i = (1); i <= (t); ++i) {
    solve();
  }
}