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;
string S;
int s;
int pset[4010];
int fs(int a) { return a == pset[a] ? a : pset[a] = fs(pset[a]); }
void connect(int a, int b) {
  pset[fs(a)] = fs(b);
  pset[fs(a ^ 1)] = fs(b ^ 1);
}
set<int> st;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> S;
  s = S.length();
  S = "?" + S;
  long long ans = 0;
  for (int i = (2); i <= (s); i++) {
    for (int j = (0); j <= (s * 4 + 1); j++) pset[j] = j;
    connect(1, 1 * 2);
    for (int j = (1); j <= (s / 2); j++) {
      connect(j * 2, (s - j + 1) * 2);
    }
    for (int j = (1); j <= (i - 1); j++) {
      connect(0, (j + s) * 2);
    }
    connect(1, (i + s) * 2);
    for (int j = (i + 1); j <= (s); j++) {
      connect((j + s) * 2, (s - (j - i) + s) * 2);
    }
    for (int j = (1); j <= (s); j++) {
      switch (S[j]) {
        case '0':
          connect(j * 2, (j + s) * 2);
          break;
        case '1':
          connect(j * 2, (j + s) * 2 ^ 1);
          break;
      }
    }
    bool valid = true;
    for (int j = 0; j <= s * 4; j += 2) {
      if (fs(j) == fs(j + 1)) {
        valid = false;
        break;
      }
    }
    if (!valid) continue;
    st.clear();
    for (int j = (0); j <= (s * 4 + 1); j++) {
      st.insert(fs(j));
    }
    long long pdt = 1;
    int pw = (int)st.size() / 2 - 1;
    for (int i = (1); i <= (pw); i++) pdt = pdt * 2 % 998244353;
    ans = (ans + pdt) % 998244353;
  }
  printf("%lld\n", ans);
  return 0;
}