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 = 3e3 + 7;
const int mod = 998244353;
int col[maxn];
namespace DSU {
int far[maxn];
void init() {
  for (int i = 0; i < maxn; i++) far[i] = i;
}
int Find(int x) { return x == far[x] ? x : far[x] = Find(far[x]); }
void Union(int x, int y) {
  x = Find(x), y = Find(y);
  if (x < y) swap(x, y);
  far[y] = x;
}
};  // namespace DSU
string s;
int var, w, b;
bool isp[maxn];
vector<int> G[maxn];
bool dfs(int u) {
  for (auto &v : G[u]) {
    if (col[v] == -1) {
      col[v] = col[u] ^ 1;
      if (!dfs(v)) return false;
    } else {
      if (col[v] == col[u]) return false;
    }
  }
  return true;
}
long long solve(int len) {
  for (int i = 0; i <= b; i++) G[i].clear();
  memset(isp, 0, sizeof(isp));
  DSU::init();
  for (int i = 0; i < s.length() / 2; i++) DSU::Union(i, s.length() - i - 1);
  for (int i = 0; i < len / 2; i++) DSU::Union(var + i, var + len - 1 - i);
  isp[w] = isp[b] = 1;
  DSU::Union(var + len - 1, b);
  for (int i = 0; i < s.length(); i++) isp[i] = 1;
  for (int i = 0; i < len; i++) isp[i + var] = 1;
  for (int i = 0; i < len; i++)
    if (s[i] == '0') DSU::Union(i, var + i);
  for (int i = len; i < s.length(); i++) {
    if (s[i] == '1')
      DSU::Union(i, b);
    else if (s[i] == '0')
      DSU::Union(i, w);
  }
  DSU::Union(s.length() - 1, b);
  if (DSU::Find(b) == DSU::Find(w)) return 0;
  for (int i = 0; i < len; i++) {
    if (s[i] == '1') {
      G[DSU::Find(i)].push_back(DSU::Find(var + i));
      G[DSU::Find(var + i)].push_back(DSU::Find(i));
    }
  }
  G[DSU::Find(w)].push_back(DSU::Find(b));
  G[DSU::Find(b)].push_back(DSU::Find(w));
  long long ret = 1;
  memset(col, -1, sizeof(col));
  for (int i = b; i >= 0; i--) {
    if (isp[i]) {
      int cur = DSU::Find(i);
      if (col[cur] == -1) {
        if (cur == b)
          col[cur] = 1;
        else
          col[cur] = 0;
        if (!dfs(cur))
          return 0;
        else {
          if (cur != b && cur != w) ret = ret * 2 % mod;
        }
      }
    }
  }
  return ret;
}
int main() {
  cin >> s;
  var = s.length();
  reverse(s.begin(), s.end());
  w = var * 2 + 1, b = var * 2 + 2;
  long long ans = 0;
  for (int i = 1; i < s.length(); i++) ans = (ans + solve(i)) % mod;
  cout << ans << endl;
}