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;
inline long long read() {
  long long x = 0, f = 1;
  char c = getchar();
  while ((c < '0' || c > '9') && (c != '-')) c = getchar();
  if (c == '-') f = -1, c = getchar();
  while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
  return x * f;
}
const int N = 2010, mod = 998244353;
int n;
char s[N];
int c[N], vis[N];
vector<pair<int, int> > e[N];
inline void init() {
  for (register int i = (1); i <= (2 * n); i++)
    e[i].clear(), c[i] = -1, vis[i] = -1;
}
inline void Add(int x, int y, int z) {
  e[x].emplace_back(y, z), e[y].emplace_back(x, z);
}
vector<int> v;
bool flag;
inline void dfs(int u, int c) {
  vis[u] = c, v.push_back(u);
  for (auto v : e[u]) {
    if (vis[v.first] == -1)
      dfs(v.first, c ^ v.second);
    else if ((vis[u] ^ v.second) != vis[v.first])
      flag = 0;
  }
}
inline int calc() {
  int ret = 1;
  for (register int i = (1); i <= (2 * n); i++)
    if (vis[i] == -1) {
      v.clear(), flag = 1, dfs(i, 0);
      if (flag == 0) return 0;
      int x = 2;
      for (auto j : v)
        if (c[j] != -1) {
          if (x == 2)
            x = (c[j] == vis[j]);
          else if ((c[j] == vis[j]) != x)
            return 0;
        }
      if (x == 2) ret = 2 * ret % mod;
    }
  return ret;
}
int main() {
  scanf("%s", s + 1), n = strlen(s + 1);
  int ans = 0;
  for (register int i = (2); i <= (n); i++) {
    init();
    for (register int j = (1); j <= (n); j++)
      if (s[j] != '?') {
        if (s[j] == '0')
          Add(j, n + j, 0);
        else
          Add(j, n + j, 1);
      }
    for (register int j = (1); j <= (n / 2); j++) Add(j, n - j + 1, 0);
    int x = n + i, y = n + n;
    while (x < y) Add(x, y, 0), x++, y--;
    c[1] = c[n] = c[n + i] = c[n + n] = 1;
    for (register int j = (1); j < (i); j++) c[n + j] = 0;
    ans = (ans + calc()) % mod;
  }
  printf("%d\n", ans);
}