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 mod = 998244353;
int n;
int a[1005];
char s[1005];
int head[1005 << 1], cnt;
int color[1005 << 1], visit[1005 << 1];
struct data {
  int next, to, type;
  data(int next = 0, int to = 0, int type = 0)
      : next(next), to(to), type(type) {}
} edge[1000005];
void connect(int u, int v, int t) {
  edge[++cnt] = data(head[u], v, t);
  head[u] = cnt;
}
bool DFS(int u) {
  for (int i = head[u]; i; i = edge[i].next) {
    int v = edge[i].to, t = edge[i].type;
    if (visit[v]) {
      if (color[v] != (color[u] ^ t)) {
        return false;
      }
      continue;
    }
    visit[v] = true;
    color[v] = color[u] ^ t;
    if (!DFS(v)) return false;
  }
  return true;
}
long long solve(int m) {
  memset(head, 0, sizeof(head));
  memset(visit, 0, sizeof(visit));
  memset(color, 0, sizeof(color));
  cnt = 0;
  for (int i = 1; i <= n; ++i) connect(i, n - i + 1, 0);
  for (int i = 1; i <= m; ++i) connect(i + n, m - i + 1 + n, 0);
  for (int i = 1; i <= n; ++i) {
    if (a[i] == 2) continue;
    connect(i, i + n, a[i]);
    connect(i + n, i, a[i]);
  }
  for (int i = m + 1; i <= n; ++i) connect((n << 1) + 1, i + n, 0);
  connect((n << 1) + 1, m + n, 1);
  connect(m + n, (n << 1) + 1, 1);
  connect((n << 1) + 1, n, 1);
  connect(n, (n << 1) + 1, 1);
  bool flag = false;
  long long res = 1;
  for (int i = (n << 1) + 1; i >= 1; --i)
    if (!visit[i]) {
      visit[i] = true;
      if (!DFS(i)) return 0;
      if (flag) res = res * 2 % mod;
      flag = true;
    }
  return res;
}
int main() {
  scanf("%s", s + 1);
  n = (int)strlen(s + 1);
  for (int i = 1; i <= n; ++i) a[n - i + 1] = s[i] == '?' ? 2 : s[i] - '0';
  long long ans = 0;
  for (int i = 1; i <= n; ++i) ans = (ans + solve(i)) % mod;
  printf("%I64d\n", ans);
}