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 = 2210;
vector<pair<int, int>> G[maxn];
char a[maxn];
const long long mod = 998244353;
int n;
void add(int u, int v, int type) {
  G[u].push_back(make_pair(v, type));
  G[v].push_back(make_pair(u, type));
}
int color[maxn];
bool init_dfs(int u, int fa) {
  int ok = 1;
  for (int i = 0; i < G[u].size(); i++) {
    pair<int, int> nex_ = G[u][i];
    int v = nex_.first, type = nex_.second;
    if (v == fa) continue;
    if (!color[v]) {
      if (type == 1)
        color[v] = 3 - color[u];
      else
        color[v] = color[u];
      int res = init_dfs(v, u);
      if (!res) return false;
    } else {
      if (type == 1) {
        if (color[u] + color[v] != 3) return false;
      } else {
        if (color[u] - color[v] != 0) return false;
      }
    }
  }
  return ok;
}
bool vis[maxn];
void dfs(int u, int fa) {
  vis[u] = 1;
  for (int i = 0; i < G[u].size(); i++) {
    int v = G[u][i].first;
    if (v == fa) continue;
    if (!vis[v]) dfs(v, u);
  }
}
void build(int k) {
  for (int i = 1; i <= n + n + 1; i++) {
    G[i].clear();
  }
  for (int i = 1; i <= n; i++) {
    if (i <= k) {
      if (a[i] != '?') {
        add(i, n + i, a[i] - '0');
      }
    } else {
      if (a[i] != '?') {
        if (a[i] == '1') add(i, n + k + 2, 0);
        if (a[i] == '0') add(i, n + k + 1, 0);
      }
    }
  }
  for (int i = 1, j = n; i < j; i++, j--) {
    add(i, j, 0);
  }
  for (int i = 1, j = k; i < j; i++, j--) {
    add(n + i, n + j, 0);
  }
  add(n + 1, 1, 0);
  add(n + k + 1, k + n + 2, 1);
}
long long handle() {
  long long res = 0;
  for (int i = 1; i <= n; i++) {
    build(i);
    memset(color, 0, sizeof(color));
    int re_ = 1;
    for (int j = 1; j <= n + i + 2; j++) {
      if (!color[j]) {
        color[j] = 1;
        re_ = init_dfs(j, -1);
        if (re_ == 0) break;
      }
    }
    if (!re_) continue;
    int cnt = 0;
    memset(vis, false, sizeof(vis));
    for (int j = 1; j <= n + i + 2; j++) {
      if (!vis[j]) {
        dfs(j, -1);
        ++cnt;
      }
    }
    --cnt;
    long long add_ = 1;
    for (int i = 1; i <= cnt; i++) add_ = add_ * 2 % mod;
    res = (res + add_) % mod;
  }
  return res;
}
int main() {
  cin >> (a + 1);
  n = strlen(a + 1);
  for (int i = 1, j = n; i < j; i++, j--) {
    swap(a[i], a[j]);
  }
  cout << handle() << endl;
  return 0;
}