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 MOD = 998244353;
string s;
vector<int> g[2010], dg[2010];
int co[2010];
long long ans = 0, res;
bool ok;
void dfs(int pos, int now) {
  if (!ok) return;
  co[pos] = now;
  for (int i = 0; i < g[pos].size(); i++) {
    if (co[g[pos][i]] != -1) {
      if (co[g[pos][i]] != now) {
        ok = false;
        return;
      }
      continue;
    }
    dfs(g[pos][i], now);
  }
  for (int i = 0; i < dg[pos].size(); i++) {
    if (co[dg[pos][i]] != -1) {
      if (co[dg[pos][i]] != (now ^ 1)) {
        ok = false;
        return;
      }
      continue;
    }
    dfs(dg[pos][i], now ^ 1);
  }
}
int main() {
  cin >> s;
  for (int len = s.size() - 1; len > 0; len--) {
    ok = true;
    for (int i = 0; i < 2005; i++) {
      co[i] = -1;
      g[i].clear();
      dg[i].clear();
    }
    for (int i = 0; i < s.size() / 2; i++) {
      g[i].push_back(s.size() - i - 1);
      g[s.size() - i - 1].push_back(i);
    }
    for (int i = 0; i < len / 2; i++) {
      g[i + s.size()].push_back(len - i - 1 + s.size());
      g[len - i - 1 + s.size()].push_back(i + s.size());
    }
    int f1 = -1, f0 = -1, l1 = -1, l0 = -1;
    for (int i = 0; i < s.size() - len; i++) {
      if (s[i] == '1') {
        if (f1 == -1) {
          f1 = l1 = i;
          continue;
        }
        g[i].push_back(l1);
        g[l1].push_back(i);
        l1 = i;
      }
      if (s[i] == '0') {
        if (f0 == -1) {
          f0 = l0 = i;
          continue;
        }
        g[i].push_back(l0);
        g[l0].push_back(i);
        l0 = i;
      }
    }
    if (l1 > -1 && l0 > -1) {
      dg[l1].push_back(l0);
      dg[l0].push_back(l1);
    }
    for (int i = s.size() - len, j = 0; i < s.size(); i++, j++) {
      if (s[i] == '1') {
        dg[i].push_back(j + s.size());
        dg[j + s.size()].push_back(i);
      }
      if (s[i] == '0') {
        g[i].push_back(j + s.size());
        g[j + s.size()].push_back(i);
      }
    }
    g[s.size()].push_back(0);
    g[0].push_back(s.size());
    int all = 0;
    for (int i = 0; i < s.size() + len; i++) {
      if (co[i] == -1) {
        dfs(i, 0);
        all++;
      }
    }
    if (!ok) continue;
    res = 1;
    for (int i = 0; i < all - 1; i++) res = res * 2 % MOD;
    ans = (ans + res) % MOD;
  }
  cout << ans << endl;
  return 0;
}