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 mod = 998244353;
int main() {
  string S;
  cin >> S;
  int ans = 0, n = S.length();
  vector<bool> vis(2 * n), a(n), b(n), s(n);
  vector<int> stk, stk2;
  for (int i = 0; i < n; ++i) s[i] = S[i] == '1';
  for (int i = 1; i < n; ++i) {
    vis.assign(2 * n, false);
    stk2.resize(2 * n), iota(stk2.begin(), stk2.end(), 0);
    int tmp = 1;
    for (int j = 0; j < i; ++j)
      vis[n + j] = true, b[j] = false, stk.push_back(n + j);
    if (i < n) vis[n + i] = true, b[i] = true, stk.push_back(n + i);
    while (!stk.empty()) {
      int x = stk.back();
      stk.pop_back();
      if (x < n) {
        if (vis[n - 1 - x]) {
          if (a[x] != a[n - 1 - x]) {
            tmp = 0, stk2.clear();
            break;
          }
        } else {
          vis[n - 1 - x] = true, a[n - 1 - x] = a[x];
          stk.push_back(n - 1 - x);
        }
        if (S[x] != '?') {
          if (vis[n + x]) {
            if (a[x] ^ b[x] ^ s[x]) {
              tmp = 0, stk2.clear();
              break;
            }
          } else {
            vis[n + x] = true, b[x] = s[x] ^ a[x];
            stk.push_back(n + x);
          }
        }
      } else {
        x -= n;
        if (2 * n - 1 - x + i < 2 * n) {
          if (vis[2 * n - 1 - x + i]) {
            if (b[x] != b[n - 1 - x + i]) {
              tmp = 0, stk2.clear();
              break;
            }
          } else {
            vis[2 * n - 1 - x + i] = true, b[n - 1 - x + i] = b[x];
            stk.push_back(2 * n - 1 - x + i);
          }
        }
        if (S[x] != '?') {
          if (vis[x]) {
            if (a[x] ^ b[x] ^ s[x]) {
              tmp = 0, stk2.clear();
              break;
            }
          } else {
            vis[x] = true, a[x] = s[x] ^ b[x];
            stk.push_back(x);
          }
        }
      }
    }
    while (!stk2.empty()) {
      int x = stk2.back();
      stk2.pop_back();
      if (vis[x]) continue;
      vis[x] = true;
      if (x < n)
        a[x] = true;
      else
        b[x - n] = true;
      stk.push_back(x);
      tmp += tmp;
      if (tmp >= mod) tmp -= mod;
      while (!stk.empty()) {
        x = stk.back();
        stk.pop_back();
        if (x < n) {
          if (vis[n - 1 - x]) {
            if (a[x] != a[n - 1 - x]) {
              tmp = 0, stk2.clear();
              break;
            }
          } else {
            vis[n - 1 - x] = true, a[n - 1 - x] = a[x];
            stk.push_back(n - 1 - x);
          }
          if (S[x] != '?') {
            if (vis[n + x]) {
              if (a[x] ^ b[x] ^ s[x]) {
                tmp = 0, stk2.clear();
                break;
              }
            } else {
              vis[n + x] = true, b[x] = s[x] ^ a[x];
              stk.push_back(n + x);
            }
          }
        } else {
          x -= n;
          if (2 * n - 1 - x + i < 2 * n) {
            if (vis[2 * n - 1 - x + i]) {
              if (b[x] != b[n - 1 - x + i]) {
                tmp = 0, stk2.clear();
                break;
              }
            } else {
              vis[2 * n - 1 - x + i] = true, b[n - 1 - x + i] = b[x];
              stk.push_back(2 * n - 1 - x + i);
            }
          }
          if (S[x] != '?') {
            if (vis[x]) {
              if (a[x] ^ b[x] ^ s[x]) {
                tmp = 0, stk2.clear();
                break;
              }
            } else {
              vis[x] = true, a[x] = s[x] ^ b[x];
              stk.push_back(x);
            }
          }
        }
      }
    }
    ans += tmp;
    if (ans >= mod) ans -= mod;
  }
  cout << ans;
}