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;
int fa[2005], f[2005], t1, t2, a[2005], ans, fans, n;
char ch[2005];
int gets() {
  int v = 0;
  char ch;
  bool f = 0;
  while (!isdigit(ch = getchar()))
    if (ch == '-') f = 1;
  v = ch - 48;
  while (isdigit(ch = getchar())) v = (v << 1) + (v << 3) + ch - 48;
  return f ? -v : v;
}
int getfa(int x) {
  if (fa[x] == x) return x;
  int t = getfa(fa[x]);
  f[x] ^= f[fa[x]];
  fa[x] = t;
  return fa[x];
}
void test(int x) {
  for (int i = 1; i <= n * 2; i++) fa[i] = i, f[i] = 0;
  fa[2 * n + 1] = 2 * n + 1, f[2 * n + 1] = 0;
  for (int i = 1; i + i <= n; i++) fa[i] = n + 1 - i, f[i] = 0;
  for (int i = 1; i + i <= x; i++) fa[i + n] = n + x + 1 - i, f[i + n] = 0;
  for (int i = x + 1; i <= n; i++) fa[i + n] = 2 * n + 1, f[i + n] = 0;
  fa[n] = 2 * n + 1, f[n] = 1;
  fa[x + n] = 2 * n + 1, f[n + x] = 1;
  for (int i = 1; i <= n; i++) {
    if (a[i] == 2) continue;
    t1 = getfa(i), t2 = getfa(i + n);
    if (t1 == t2) {
      if ((f[i] ^ f[i + n]) == a[i]) continue;
      return;
    }
    if (t1 > t2) swap(t1, t2);
    if (a[i] == 1) {
      fa[t1] = t2, f[t1] = 1 ^ f[i] ^ f[i + n];
    } else
      fa[t1] = t2, f[t1] = f[i] ^ f[i + n];
  }
  ans = 1;
  for (int i = 1; i <= 2 * n; i++)
    if (fa[i] == i) ans <<= 1, ans %= 998244353;
  fans = (fans + ans) % 998244353;
}
int main() {
  scanf("%s", ch + 1);
  n = strlen(ch + 1);
  for (int i = 1; i <= n; i++) a[n + 1 - i] = ch[i] == '?' ? 2 : ch[i] - '0';
  for (int i = 1; i <= n - 1; i++) test(i);
  cout << fans << endl;
  return 0;
}