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 long long MOD = 998244353;
const int INF = 2e9;
const long long INFLL = 1e18;
const int MAX_N = 2010;
string str;
int N, L;
vector<pair<int, int> > gp[MAX_N + 1];
long long ans;
vector<pair<int, int> > vt;
int type[MAX_N + 1];
bool dfs(int x) {
  for (pair<int, int> i : gp[x]) {
    if (type[i.first] == 0) {
      if (i.second == 1) {
        type[i.first] = type[x];
      } else {
        type[i.first] = 3 - type[x];
      }
      if (!dfs(i.first)) return false;
    } else {
      if (i.second == 1) {
        if (type[i.first] != type[x]) return false;
      } else {
        if (type[i.first] == type[x]) return false;
      }
    }
  }
  return true;
}
int main() {
  cin >> str;
  N = str.size();
  for (L = 1; L < N; L++) {
    while (!vt.empty()) vt.pop_back();
    for (int i = 1; i <= N + L; i++) {
      type[i] = 0;
      while (!gp[i].empty()) gp[i].pop_back();
    }
    for (int i = 1; i < (N + 2) / 2; i++) {
      gp[i].push_back({N - i + 1, 1});
      gp[N - i + 1].push_back({i, 1});
    }
    for (int i = 1; i < (L + 2) / 2; i++) {
      gp[N + i].push_back({N + L - i + 1, 1});
      gp[N + L - i + 1].push_back({N + i, 1});
    }
    int idx1 = N, idx2 = N + L;
    for (int i = N - 1; i >= 0; i--) {
      if (idx2 > N) {
        if (str[i] == '1') {
          gp[idx1].push_back({idx2, 0});
          gp[idx2].push_back({idx1, 0});
        } else if (str[i] == '0') {
          gp[idx1].push_back({idx2, 1});
          gp[idx2].push_back({idx1, 1});
        }
      } else {
        if (str[i] == '1') {
          vt.push_back({idx1, 1});
        } else if (str[i] == '0') {
          vt.push_back({idx1, 0});
        }
      }
      idx1--;
      idx2--;
    }
    vt.push_back({N + 1, 1});
    bool tf = true;
    long long sum = 1;
    while (!vt.empty()) {
      pair<int, int> now = vt.back();
      vt.pop_back();
      if (type[now.first] == 0) {
        type[now.first] = now.second + 1;
        if (!dfs(now.first)) {
          tf = false;
          break;
        }
      } else {
        if (type[now.first] != now.second + 1) {
          tf = false;
          break;
        }
      }
    }
    if (!tf) continue;
    for (int i = 1; i <= N + L; i++) {
      if (type[i] == 0) {
        sum = (sum * 2LL) % MOD;
        type[i] = 1;
        if (!dfs(i)) {
          tf = false;
          break;
        }
      }
    }
    if (tf) {
      ans = (ans + sum) % MOD;
    }
  }
  cout << ans;
  return 0;
}