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;
long long MOD = 998244353;
string S;
int N;
int cons[2010];
queue<int> Q;
int p[2010];
int tot_islands;
long long ans;
long long M2[2010];
int par(int x) { return (p[x] == x) ? x : p[x] = par(p[x]); }
void merge(int a, int b) {
  a = par(a);
  b = par(b);
  if (a == b) return;
  tot_islands--;
  p[a] = b;
}
int main() {
  cin >> S;
  N = (int)S.size();
  M2[0] = 1;
  for (int i = 1; i <= 2 * N; ++i) {
    M2[i] = (M2[i - 1] * 2) % MOD;
  }
  reverse(S.begin(), S.end());
  S = '0' + S;
  for (int len = 1; len <= N; ++len) {
    tot_islands = 0;
    for (int i = 1; i <= 2 * N; ++i) p[i] = i;
    while ((int)Q.size()) Q.pop();
    memset(cons, -1, sizeof(cons));
    for (int i = len + 1; i <= N; ++i) {
      cons[N + i] = 0;
      Q.push(N + i);
    }
    cons[N] = 1;
    Q.push(N);
    cons[len + N] = 1;
    Q.push(len + N);
    bool fail = 0;
    while ((int)Q.size()) {
      int t = Q.front();
      Q.pop();
      int side = (t - 1) / N;
      int ind = t % N;
      if (ind == 0) ind = N;
      if (side == 0) {
        int opp = N + 1 - ind;
        if (cons[opp] == -1) {
          cons[opp] = cons[t];
          Q.push(opp);
        } else if (cons[opp] != cons[t]) {
          fail = 1;
          break;
        }
        int o2 = ind + N;
        if (S[ind] == '?') continue;
        int c = S[ind] - '0';
        if (cons[o2] == -1) {
          cons[o2] = c ^ cons[t];
          Q.push(o2);
        }
        if ((cons[o2] ^ cons[t]) == c) continue;
        fail = 1;
        break;
      } else {
        if (ind <= len) {
          int opp = N + (len + 1 - ind);
          if (cons[opp] == -1) {
            cons[opp] = cons[t];
            Q.push(opp);
          } else if (cons[opp] != cons[t]) {
            fail = 1;
            break;
          }
        }
        int o2 = ind;
        if (S[ind] == '?') continue;
        int c = S[ind] - '0';
        if (cons[o2] == -1) {
          cons[o2] = c ^ cons[t];
          Q.push(o2);
        }
        if ((cons[o2] ^ cons[t]) == c) continue;
        fail = 1;
        break;
      }
    }
    if (fail == 1) continue;
    for (int i = 1; i <= 2 * N; ++i) {
      if (cons[i] != -1) continue;
      ++tot_islands;
      int side = (i - 1) / N;
      int ind = i % N;
      if (ind == 0) ind = N;
      if (side == 0) {
        merge(i, N + 1 - ind);
        if (S[ind] != '?') merge(i, ind + N);
      } else {
        if (S[ind] != '?') merge(i, ind);
        if (ind <= len) merge(i, N + len + 1 - ind);
      }
    }
    ans += M2[tot_islands];
    ans %= MOD;
  }
  cout << ans;
}