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 N = 2000;
struct node {
  int to, nxt, cost;
} sq[200200];
int all = 0, head[2020];
void add(int u, int v, int w) {
  all++;
  sq[all].to = v;
  sq[all].nxt = head[u];
  sq[all].cost = w;
  head[u] = all;
  all++;
  sq[all].to = u;
  sq[all].nxt = head[v];
  sq[all].cost = w;
  head[v] = all;
}
int n, tot = 0, dis[2020], flag;
long long bin[2020];
char s[2020];
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while ((ch < '0') || (ch > '9')) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while ((ch >= '0') && (ch <= '9')) {
    x = x * 10 + (ch - '0');
    ch = getchar();
  }
  return x * f;
}
void dfs(int u, int now) {
  dis[u] = now;
  int i;
  for (i = head[u]; i; i = sq[i].nxt) {
    int v = sq[i].to;
    if (dis[v] != -1) {
      if (dis[u] ^ dis[v] ^ sq[i].cost) flag = 1;
    } else
      dfs(v, now ^ sq[i].cost);
  }
}
long long work(int m) {
  all = 0;
  flag = 0;
  tot = 0;
  memset(head, 0, sizeof(head));
  memset(dis, -1, sizeof(dis));
  for (int i = 1; i <= n / 2; i++) add(i, n - i + 1, 0);
  for (int i = 1; i <= m / 2; i++) add(i + n, m - i + 1 + n, 0);
  for (int i = 1; i <= m; i++)
    if (s[i] != '?') add(i, i + n, s[i] - '0');
  for (int i = m + 1; i <= n; i++)
    if (s[i] != '?') add(i, n + m + 1 + (s[i] == '1'), 0);
  add(n, n + m + 2, 0);
  add(n + m, n + m + 2, 0);
  add(n + m + 1, n + m + 2, 1);
  for (int i = 1; i <= n + m + 2; i++)
    if (dis[i] == -1) {
      tot++;
      dfs(i, 0);
    }
  if (flag)
    return 0;
  else
    return bin[tot - 1];
}
int main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  bin[0] = 1;
  reverse(s + 1, s + 1 + n);
  for (int i = 1; i <= N; i++) bin[i] = (bin[i - 1] * 2) % 998244353;
  long long ans = 0;
  for (int i = 1; i <= n - 1; i++) {
    ans = (ans + work(i)) % 998244353;
  }
  printf("%I64d", ans);
  return 0;
}