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 llINF = 9223372036854775807;
const int INF = 2147483647;
const int maxn = 2e3 + 7;
const int maxm = 5e4 + 7;
const long long mod = 998244353;
const double pi = acos(-1.0);
const double eps = 1e-12;
vector<pair<int, int> > pic[maxn];
int val[maxn];
vector<int> dfn;
bool vis[maxn];
int n;
char s[maxn];
int ans;
int ind_a[maxn], ind_b[maxn];
void dfs(int cur) {
  dfn.push_back(cur);
  vis[cur] = true;
  for (int i = 0; i < pic[cur].size(); i++)
    if (!vis[pic[cur][i].first]) dfs(pic[cur][i].first);
}
bool check(int cur, int col) {
  vis[cur] = true;
  val[cur] = col;
  for (int i = 0; i < pic[cur].size(); i++) {
    int v = pic[cur][i].first;
    if (val[v] != -1 && (val[cur] + pic[cur][i].second) % 2 != val[v])
      return false;
    if (!vis[v])
      if (!check(v, (val[cur] + pic[cur][i].second) % 2)) return false;
  }
  return true;
}
int main(int argc, char const *argv[]) {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  reverse(s + 1, s + 1 + n);
  for (int m = 1; m < n; m++) {
    for (int j = 1; j <= n; j++) ind_a[j] = j;
    for (int j = 1; j <= m; j++) ind_b[j] = n + j;
    for (int i = 1; i <= n + m; i++) {
      val[i] = -1;
      pic[i].clear();
    }
    for (int i = 1; i <= n; i++) {
      pic[ind_a[i]].push_back(make_pair(ind_a[n - i + 1], 0));
      pic[ind_a[n - i + 1]].push_back(make_pair(ind_a[i], 0));
    }
    for (int i = 1; i <= m; i++) {
      pic[ind_b[i]].push_back(make_pair(ind_b[m - i + 1], 0));
      pic[ind_b[m - i + 1]].push_back(make_pair(ind_b[i], 0));
    }
    for (int i = 1; i <= n; i++) {
      if (s[i] == '?') continue;
      if (i <= m) {
        pic[ind_a[i]].push_back(make_pair(ind_b[i], s[i] - '0'));
        pic[ind_b[i]].push_back(make_pair(ind_a[i], s[i] - '0'));
      } else {
        val[ind_a[i]] = s[i] - '0';
      }
    }
    val[n + m] = 1;
    memset(vis, false, sizeof(vis));
    int cnt = 1;
    for (int i = 1; i <= n + m; i++) {
      if (!vis[i]) {
        dfn.clear();
        dfs(i);
        int start = i, value = -1;
        for (int j = 0; j < dfn.size(); j++) {
          int x = dfn[j];
          if (val[x] != -1) {
            start = x;
            value = val[x];
          }
          vis[x] = 0;
        }
        if (value != -1) {
          cnt = (cnt * check(start, value)) % mod;
        } else {
          cnt = (cnt * 2 * check(start, 0)) % mod;
        }
      }
    }
    ans = (ans + cnt) % mod;
  }
  printf("%d\n", ans);
  return 0;
}