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 int MAXN = 1010, MOD = 998244353;
char s[MAXN];
int N;
long long answer = 0;
vector<int> adj_same[MAXN * 3], adj_diff[MAXN * 3];
vector<bool> vis;
void mark_same(int x, int y) {
  ;
  adj_same[x].push_back(y);
  adj_same[y].push_back(x);
}
void mark_diff(int x, int y) {
  ;
  adj_diff[x].push_back(y);
  adj_diff[y].push_back(x);
}
void recurse(int a, int b, int i) {
  if (vis[i]) return;
  vis[i] = true;
  if (i < a + 2) {
    int aidx = i - 2;
    if (aidx >= b) {
      if (s[aidx] == '1') {
        mark_same(1, 2 + aidx);
      } else if (s[aidx] == '0') {
        mark_same(0, 2 + aidx);
      }
    } else {
      int bidx = aidx;
      if (s[aidx] == '1') {
        mark_diff(2 + aidx, 2 + a + bidx);
      } else if (s[aidx] == '0') {
        mark_same(2 + aidx, 2 + a + bidx);
      }
      recurse(a, b, 2 + a + bidx);
    }
    mark_same(2 + aidx, 2 + a - aidx - 1);
    recurse(a, b, 2 + a - aidx - 1);
  } else {
    int bidx = i - a - 2;
    int aidx = bidx;
    if (s[aidx] == '1') {
      mark_diff(2 + aidx, 2 + a + bidx);
    } else if (s[aidx] == '0') {
      mark_same(2 + aidx, 2 + a + bidx);
    }
    recurse(a, b, 2 + aidx);
    mark_same(2 + a + bidx, 2 + a + b - bidx - 1);
    recurse(a, b, 2 + a + b - bidx - 1);
  }
}
vector<vector<int>> component;
vector<int> cnum;
bool bad = false;
void flood(int i, int comp, int counterpart) {
  if (bad) return;
  if (vis[i]) {
    if (cnum[i] != comp) {
      bad = true;
    }
    return;
  } else {
    vis[i] = true;
    cnum[i] = comp;
    component[comp].push_back(i);
    for (int j = 0; j < adj_same[i].size(); ++j) {
      flood(adj_same[i][j], comp, counterpart);
    }
    for (int j = 0; j < adj_diff[i].size(); ++j) {
      flood(adj_diff[i][j], counterpart, comp);
    }
  }
}
void solve(int a, int b) {
  ;
  for (int k = 0; k < a + b + 2; ++k) {
    adj_same[k].clear();
    adj_diff[k].clear();
    vis[k] = false;
    cnum[k] = -1;
  }
  bad = false;
  component.clear();
  mark_diff(0, 1);
  mark_same(1, 2);
  mark_same(1, 2 + a);
  vis[1] = true;
  vis[0] = true;
  for (int i = 0; i < a; ++i) {
    recurse(a, b, i + 2);
  }
  for (int i = 0; i < a + b + 2; ++i) {
    vis[i] = false;
  }
  for (int i = 0; i < a + b + 2; ++i) {
    if (!vis[i]) {
      int next = component.size();
      component.push_back(vector<int>());
      component.push_back(vector<int>());
      flood(i, next, next + 1);
    }
  }
  if (!bad) {
    int count = (component.size() - 2) / 2;
    ;
    int pow = 1;
    for (int i = 0; i < count; ++i) {
      pow = (pow * 2) % MOD;
    }
    answer = (answer + pow) % MOD;
  }
}
int main() {
  scanf("%s", s);
  N = strlen(s);
  vis.resize(2 * N + 2, false);
  cnum.resize(2 * N + 2, -1);
  for (int i = 0; i < N / 2; ++i) {
    char temp = s[i];
    s[i] = s[N - 1 - i];
    s[N - i - 1] = temp;
  }
  for (int b = 1; b <= N; ++b) {
    solve(N, b);
  }
  printf("%lld\n", answer);
  return 0;
}