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>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize(2)
#pragma G++ optimize(2)
using namespace std;
constexpr long long N = 1e3 + 9;
constexpr long long M = 998244353;
constexpr long long INF = 0x3f3f3f3f3f3f3f3f;
constexpr long long INF2 = 0xcfcfcfcfcfcfcfcf;
char s[N];
long long n;
long long tot;
struct E {
  long long u, v, w;
} e[N * 20];
vector<long long> g[N * 20];
long long color[N * 20];
void addEdge(long long u, long long v, long long w) {
  e[++tot] = {u, v, w};
  g[u].emplace_back(tot);
  g[v].emplace_back(tot);
}
void build(long long la) {
  for (long long i = 1; i <= n + n + 2; i++) g[i].clear();
  tot = 0;
  addEdge(1, 2, 1);
  for (long long i = 1; i < la + 1 - i; i++) {
    addEdge(2 + i, 2 + la + 1 - i, 0);
  }
  for (long long i = 1; i < n + 1 - i; i++) {
    addEdge(2 + la + i, 2 + la + n + 1 - i, 0);
  }
  for (long long i = 1; i <= n; i++) {
    long long lz = n - la;
    long long a = 2 + i - lz, b = 2 + la + i;
    if (i <= lz) a = 1;
    if (s[i] != '?') addEdge(a, b, s[i] - '0');
  }
  addEdge(2, 2 + la + 1, 0);
  addEdge(2, 2 + 1, 0);
}
bool dfs(long long u, long long c) {
  color[u] = c;
  for (long long i : g[u]) {
    long long v = u ^ e[i].u ^ e[i].v;
    long long tc = e[i].w ? 3 - c : c;
    if (!color[v]) {
      if (!dfs(v, tc)) return false;
    } else if (color[v] != tc)
      return false;
  }
  return true;
}
long long qpow(long long x) {
  long long c = 1, a = 2;
  while (x) {
    if (x & 1) c = c * a % M;
    a = a * a % M;
    x >>= 1;
  }
  return c;
}
long long solve(long long la) {
  long long ans = 0;
  memset(color, 0, sizeof(color));
  for (long long i = 1; i <= 2 + la + n; i++) {
    if (!color[i]) {
      if (dfs(i, 1))
        ans++;
      else
        return 0;
    }
  }
  return qpow(ans - 1);
}
signed main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  ;
  cin >> (s + 1);
  n = strlen(s + 1);
  long long ans = 0;
  for (long long la = 1; la <= n; la++) {
    build(la);
    ans = (ans + solve(la)) % M;
  }
  cout << ans << endl;
  return 0;
}