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>
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target( \
    "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
using namespace std;
int cd, kq, mod = 998244353, code[300], vis[2005], found, w[2005][2005],
            val[2005];
vector<int> edge[2005];
string s;
void add(int st, int en, int bonus) {
  while (st < en) {
    edge[st + bonus].push_back(en + bonus);
    edge[en + bonus].push_back(st + bonus);
    w[st + bonus][en + bonus] = w[en + bonus][st + bonus] = 0;
    st++;
    en--;
  }
}
void create_graph() {
  add(1, cd, 0);
  for (int i = 1; i <= cd; i++) {
    edge[i].push_back(i + cd);
    w[i][i + cd] = w[i + cd][i] = code[s[i]];
  }
}
int ope(int val, int change) {
  if (val == 3 || change == 3) return 3;
  if (change == 0) return val;
  if (change == 1) return (val + 1) % 2;
}
void dfs(int u) {
  vis[u] = 1;
  for (auto v : edge[u]) {
    int change = w[u][v];
    int new_val = ope(val[u], change);
    if (new_val == 3)
      if (vis[v] != 1 && val[v] != 3) dfs(v);
    if (found == -1) return;
    if (new_val != 3) {
      if (val[v] != 3 && val[v] != new_val) {
        found = -1;
        return;
      }
      if (vis[v] != 1) val[v] = new_val, dfs(v);
    }
  }
}
void component(int u) {
  vis[u] = 2;
  for (auto v : edge[u]) {
    if (vis[v] == 2 || w[u][v] == 3) continue;
    component(v);
  }
}
void reset(int st) {
  found = 0;
  for (int i = 1; i <= 2 * cd; i++) {
    val[i] = 3;
    vis[i] = 0;
    if (i > cd) edge[i].clear();
  }
  for (int i = 1; i <= cd; i++) {
    edge[i + cd].push_back(i);
    w[i][i + cd] = w[i + cd][i] = code[s[i]];
  }
  for (int i = 2; i <= st; i++) val[i + cd] = 0;
  add(st, cd, cd);
  val[st + cd] = val[1] = 1;
}
int get(int st) {
  reset(st);
  for (int i = 1; i <= 2 * cd; i++) {
    if (vis[i] == 0 && val[i] != 3) dfs(i);
    if (found == -1) return 0;
  }
  int result = 1, co = 0;
  for (int i = 1; i <= 2 * cd; i++)
    if (vis[i] != 2 && val[i] == 3) co++, component(i);
  for (int i = 1; i <= co; i++) result = 2ll * result % mod;
  return result;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> s;
  cd = s.size();
  s = '0' + s;
  code['0'] = 0, code['1'] = 1, code['?'] = 3;
  create_graph();
  for (int i = 2; i <= cd; i++) kq += get(i), kq %= mod;
  cout << kq << endl;
}