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>
#pragma warning(disable : 4996)
const long long MOD = 998244353;
using namespace std;
long long mpow(long long x, long long n) {
  long long ans = 1;
  while (n != 0) {
    if (n & 1) ans = ans * x % MOD;
    x = x * x % MOD;
    n = n >> 1;
  }
  return ans;
}
long long minv(long long x) { return mpow(x, MOD - 2); }
class UF {
 private:
  int num;
  vector<int> par;
  vector<int> siz;
  vector<int> wt;

 public:
  vector<long long> parval;

 public:
  UF(int n) : num(n) {
    par.resize(n);
    siz.resize(n);
    wt.resize(n);
    parval.resize(n);
    int i;
    for (i = 0; i < n; i++) {
      par[i] = i;
      siz[i] = 1;
      wt[i] = 0;
      parval[i] = 0;
    }
  }
  int find(int x) {
    int p = par[x];
    if (x == p) {
      return x;
    }
    int q = find(p);
    int diff = (wt[q] ^ wt[p]);
    wt[x] ^= diff;
    return par[x] = q;
  }
  bool unite(int x, int y, int diff) {
    int px = find(x);
    int py = find(y);
    int diff0 = (wt[y] ^ wt[x]);
    diff ^= diff0;
    x = find(x);
    y = find(y);
    if (x == y) {
      return (wt[y] == (wt[x] ^ diff));
    }
    if (siz[x] < siz[y]) {
      par[x] = y;
      siz[y] = siz[x] + siz[y];
      wt[x] = diff;
    } else {
      par[y] = x;
      siz[x] = siz[x] + siz[y];
      wt[y] = diff;
    }
    return true;
  }
  bool same(int x, int y) { return find(x) == find(y); }
  int size(int x) { return siz[find(x)]; }
  int GetWt(int x) {
    int p = find(x);
    return wt[x];
  }
  int ngroup() {
    int count = 0;
    int i;
    for (i = 0; i < num; i++) {
      if (par[i] == i) {
        count++;
      }
    }
    return count;
  }
  void print() {
    int i;
    printf("par: ");
    for (i = 0; i < num; i++) printf("%d ", par[i]);
    printf("\n");
    printf("wt:  ");
    for (i = 0; i < num; i++) printf("%d ", GetWt(i));
    printf("\n");
  }
};
char str[1005];
void solve() {
  scanf("%s", str);
  int n = (int)strlen(str);
  long long ans = 0;
  int i, k;
  for (i = 1; i < n; i++) {
    int num = n + n - i;
    int n0 = n - i;
    UF uf(num + 1);
    int bad = 0;
    for (k = 0; k < n / 2; k++) {
      if (!uf.unite(k, n - 1 - k, 0)) bad = 1;
    }
    for (k = n; k < n + (n0 / 2); k++) {
      if (!uf.unite(k, n + n + n0 - 1 - k, 0)) bad = 1;
    }
    for (k = 0; k < n; k++) {
      if (k < i && str[k] != '?') {
        if (!uf.unite(k, num, str[k] - '0')) bad = 1;
      } else if (k >= i && str[k] != '?') {
        if (!uf.unite(k, n + k - i, str[k] - '0')) bad = 1;
      }
    }
    if (!uf.unite(n, num, 1)) bad = 1;
    if (bad == 0) {
      ans = (ans + mpow(2, uf.ngroup() - 1)) % MOD;
    }
  }
  printf("%lld\n", ans);
  return;
}
int main() {
  solve();
  return 0;
}