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 inf = 0x3f3f3f3f;
const long long linf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
const double pi = 3.14159265358979;
const int maxn = 1e5 + 5;
const int maxm = 1e7 + 233;
const int mod = 998244353;
struct edge {
  int to, nxt, w;
} edge[maxn << 1];
int tot, head[maxn << 1];
void init() {
  tot = 0;
  memset(head, -1, sizeof head);
}
void addedge(int u, int v, int w) {
  edge[tot].to = v;
  edge[tot].w = w;
  edge[tot].nxt = head[u];
  head[u] = tot++;
  edge[tot].to = u;
  edge[tot].w = w;
  edge[tot].nxt = head[v];
  head[v] = tot++;
}
int col[maxn];
bool dfs(int u, int w) {
  col[u] = w;
  for (int i = head[u]; ~i; i = edge[i].nxt) {
    int v = edge[i].to;
    if (col[v] != -1) {
      if (col[v] != (edge[i].w ^ w)) return false;
    } else if (!dfs(v, edge[i].w ^ w))
      return false;
  }
  return true;
}
long long pow_(long long a, long long b) {
  long long ret = 1;
  while (b) {
    if (b & 1) ret = ret * a % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return ret;
}
char s[1005];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> (s + 1);
  int n = strlen(s + 1);
  reverse(s + 1, s + 1 + n);
  int ans = 0;
  for (int m = 1; m <= n - 1; ++m) {
    init();
    for (int i = 1; i <= n / 2; ++i) addedge(i, n - i + 1, 0);
    for (int i = 1; i <= m / 2; ++i) addedge(n + i, n + m - i + 1, 0);
    addedge(n + 1, n + n + 2, 0);
    addedge(n + 1, n + m + 1, 1);
    addedge(n + m, n + n + 2, 0);
    addedge(n + m, n + m + 1, 1);
    for (int i = 1; i <= m; ++i)
      if (s[i] == '1')
        addedge(i, n + i, 1);
      else if (s[i] == '0')
        addedge(i, n + i, 0);
    for (int i = m + 1; i <= n; ++i)
      if (s[i] == '1')
        addedge(i, n + m + 2, 0), addedge(i, n + m + 1, 1);
      else if (s[i] == '0')
        addedge(i, n + m + 1, 0), addedge(i, n + m + 2, 1);
    memset(col, -1, sizeof col);
    int c = 0;
    for (int i = 1; i <= n + m + 2; ++i) {
      if (col[i] == -1) {
        if (dfs(i, 0))
          ++c;
        else {
          c = 0;
          break;
        }
      }
    }
    if (c) ans = (ans + pow_(2, c - 1)) % mod;
  }
  cout << ans << '\n';
  return 0;
}