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;
using lli = long long;
using lld = long double;
using ulli = unsigned long long int;
using pll = pair<lli, lli>;
using ttt = pair<lli, pll>;
using vttt = vector<ttt>;
using vll = vector<pll>;
using vl = vector<lli>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using cd = complex<lld>;
const double PI = acos(-1);
inline lli mpow(lli a, lli b, lli m = 998244353) {
  lli ans = 1;
  while (b) {
    if (b & 1) ans = (ans * a) % m;
    a = (a * a) % m;
    b /= 2;
  }
  return ans;
}
string s;
lli n;
bool vis[2002], fl;
int color[2002];
vvi adjs, adjd;
void dfs(int v) {
  vis[v] = 1;
  for (auto& x : adjs[v])
    if (!vis[x]) {
      if (color[x] && color[x] != color[v]) {
        fl = 1;
      } else {
        color[x] = color[v];
        dfs(x);
      }
    }
  for (auto& x : adjd[v])
    if (!vis[x]) {
      if (color[x] == color[v]) {
        fl = 1;
      } else {
        color[x] = 3 - color[v];
        dfs(x);
      }
    }
}
lli process(int as) {
  for (int i = 0; i < n + as; i++) vis[i] = color[i] = 0;
  adjs = vvi(n + as);
  adjd = vvi(n + as);
  fl = 0;
  for (int i = 0; i < n - as; i++) {
    if (s[i] == '1') color[i] = 1;
    if (s[i] == '0') color[i] = 2;
  }
  color[n] = 1;
  for (int i = 0; i < n; i++) adjs[i].push_back(n - i - 1);
  for (int i = 0; i < as; i++) adjs[i + n].push_back(as - i - 1 + n);
  for (int i = n - as; i < n; i++) {
    if (s[i] == '1') {
      adjd[i].push_back(i + as);
      adjd[i + as].push_back(i);
    }
    if (s[i] == '0') {
      adjs[i].push_back(i + as);
      adjs[i + as].push_back(i);
    }
  }
  lli ans = 1;
  for (int i = 0; i < n + as; i++) {
    if (!vis[i] && color[i]) dfs(i);
  }
  for (int i = 0; i < n + as; i++) {
    if (!vis[i]) {
      color[i] = 1;
      dfs(i);
      ans = (ans * 2) % 998244353;
    }
  }
  if (fl) return 0;
  return ans;
}
int tejas_919(int kkkk) {
  lli m, k, q, u, v, temp = 0, ans = 0;
  cin >> s;
  n = ((lli)(s).size());
  for (int i = 1; i < n; i++) ans += process(i);
  ans %= 998244353;
  cout << ans << '\n';
  return 0;
}
signed main() {
  if (!0) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
  }
  cout << fixed << setprecision(10);
  int t = 1;
  for (int i = 0; i < t; i++) {
    tejas_919(i + 1);
  }
  {};
}