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 = 1005;
const int maxm = 2e5 + 10;
const int mod = 998244353;
inline int ksm(int x, int y) {
  int res = 1;
  while (y) {
    if (y & 1) res = 1ll * x * res % mod;
    x = 1ll * x * x % mod;
    y >>= 1;
  }
  return res;
}
char s[maxn];
int n, ans, beg[maxn << 1], nex[maxm], to[maxm], e;
inline void add(int x, int y) {
  e++;
  nex[e] = beg[x];
  beg[x] = e;
  to[e] = y;
  e++;
  nex[e] = beg[y];
  beg[y] = e;
  to[e] = x;
}
int f[maxn << 1], inv[maxn << 1], col[maxn << 1], cnt;
inline int find(int x) { return x == f[x] ? x : (f[x] = find(f[x])); }
inline int link(int x, int y) { f[find(x)] = find(y); }
int vis[maxn], tag[maxn], flag, tot;
inline void dfs(int x, int tg) {
  vis[x] = 1;
  tag[x] = tg;
  for (int i = beg[x]; i; i = nex[i]) {
    int t = to[i];
    if (vis[t] && tag[t] == tag[x]) flag = 0;
    if (!vis[t]) dfs(t, 3 - tg);
  }
}
int main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  for (int i = 2; i <= n; i++) {
    memset(beg, 0, sizeof(beg));
    e = 0;
    for (int j = 0; j <= 2 * n + 1; j++) f[j] = j;
    link(2, 1);
    link(3, 0);
    link(2 * i + 1, 1);
    for (int j = 2; j < i; j++) link(2 * j + 1, 0);
    for (int j = 1; j <= n / 2; j++) link(2 * j, 2 * (n - j + 1));
    for (int j = i; j <= (n + i) / 2; j++) link(2 * j + 1, 2 * (n - j + i) + 1);
    for (int j = 1; j <= n; j++)
      if (s[j] == '0') link(2 * j, 2 * j + 1);
    memset(inv, 0, sizeof(inv));
    cnt = 0;
    for (int j = 0; j <= 2 * n + 1; j++) {
      if (!inv[find(j)]) inv[find(j)] = ++cnt;
      col[j] = inv[find(j)];
    }
    add(col[0], col[1]);
    for (int j = 1; j <= n; j++)
      if (s[j] == '1') add(col[2 * j], col[2 * j + 1]);
    memset(vis, 0, sizeof(vis));
    memset(tag, 0, sizeof(tag));
    flag = 1, tot = 0;
    for (int j = 1; j <= cnt; j++)
      if (!vis[j]) dfs(j, 1), tot++;
    if (!flag) continue;
    ans = (ans + ksm(2, tot - 1)) % mod;
  }
  printf("%d\n", ans);
  return 0;
}