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 N = 2e3 + 5;
const long long mod = 998244353;
char s[N];
vector<pair<int, int> > son[N];
int vis[N];
int dfs(int x, int fa, int c) {
  vis[x] = c;
  for (pair<int, int> ne : son[x]) {
    if (ne.first == fa) continue;
    if (~vis[ne.first]) {
      if (vis[ne.first] ^ ne.second ^ vis[x]) return 0;
    } else {
      if (!dfs(ne.first, x, vis[x] ^ ne.second)) return 0;
    }
  }
  return 1;
}
long long p[N];
int main() {
  p[0] = 1;
  for (int i = 1; i < N; i++) p[i] = p[i - 1] * 2 % mod;
  scanf("%s", s + 1);
  int n;
  n = strlen(s + 1);
  reverse(s + 1, s + 1 + n);
  long long ans = 0;
  for (int m = 1; m < n; m++) {
    int head = n + m + 1;
    for (int j = 1; j <= head; j++) son[j].clear();
    son[head].push_back({n, 1}), son[n].push_back({head, 1});
    son[head].push_back({n + m, 1}), son[n + m].push_back({head, 1});
    for (int i = 1; i <= n / 2; i++) {
      son[i].push_back({n - i + 1, 0});
      son[n - i + 1].push_back({i, 0});
    }
    for (int i = 1; i <= m / 2; i++) {
      son[i + n].push_back({n + m - i + 1, 0});
      son[n + m - i + 1].push_back({i + n, 0});
    }
    for (int i = 1; i <= m; i++) {
      if (s[i] != '?') {
        son[i].push_back({i + n, s[i] - '0'});
        son[i + n].push_back({i, s[i] - '0'});
      }
    }
    for (int i = m + 1; i <= n; i++) {
      if (s[i] != '?') {
        son[head].push_back({i, s[i] - '0'});
        son[i].push_back({head, s[i] - '0'});
      }
    }
    memset(vis, -1, sizeof vis);
    int num = 0;
    for (int i = head; i; i--) {
      int f = 0;
      if (vis[i] != -1) continue;
      f = dfs(i, 0, 0);
      if (f == 0) {
        num = 0;
        break;
      }
      num++;
    }
    if (num) ans = (ans + p[num - 1]) % mod;
  }
  printf("%lld\n", ans);
  return 0;
}