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 = 2005, mod = 998244353;
char s[N];
vector<pair<int, int>> e[N << 1];
int n, fl, vis[N], col[N];
void dfs(int u, int c) {
  if (vis[u]) {
    if (c != col[u]) return (void)(fl = 0);
    return;
  }
  col[u] = c, vis[u] = 1;
  for (auto p : e[u]) dfs(p.first, c ^ p.second);
}
void add(int i, int j, int k) {
  e[i].push_back({j, k}), e[j].push_back({i, k});
}
signed main() {
  cin >> (s + 1);
  int sum = 0;
  n = strlen(s + 1);
  for (int len = 1; len < n; ++len) {
    for (int i = 1; i <= n + n + 2; ++i) e[i].clear(), col[i] = vis[i] = 0;
    for (int i = 1; i <= n / 2; ++i) add(i, n - i + 1, 0);
    for (int i = 1; i <= len / 2; ++i) add(i + n, n + len - i + 1, 0);
    for (int i = len + 1; i <= n; ++i) add(n + i, n + n + 2, 0);
    add(1, n + n + 1, 0), add(n + 1, n + n + 1, 0);
    for (int i = 1; i <= n; ++i) {
      int u = n - i + 1;
      if (s[u] == '?') continue;
      add(i + n, i, s[u] - '0');
    }
    fl = 1;
    int cnt = 0;
    for (int i = 1; i <= n + n; ++i)
      if (!vis[i]) dfs(i, 0), ++cnt;
    int ans = fl;
    for (int i = 1; i < cnt; ++i) ans = (ans + ans) % mod;
    sum = (sum + ans) % mod;
  }
  cout << sum;
}