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 = 2e3 + 15;
const int mod = 998244353;
char s[N];
int len;
int depth[N];
vector<int> adj[N];
int dp[N][2];
int add(int x, int y) { return ((x + y) % mod + mod) % mod; }
int mul(int x, int y) { return (long long)x * y % mod; }
int mypow(int x, int c) {
  int ret = 1;
  while (c > 0) {
    if (c & 1) {
      ret = mul(ret, x);
    }
    c /= 2;
    x = mul(x, x);
  }
  return ret;
}
bool vis[N];
void dfs(int node, int par) {
  vis[node] = true;
  for (int ch : adj[node]) {
    if (ch != par && !vis[ch]) {
      depth[ch] = depth[node] + 1;
      dfs(ch, node);
    }
  }
}
int solveDp(int node, int bit) {
  int &ret = dp[node][bit];
  if (ret != -1) {
    return ret;
  }
  ret = 0;
  bool isLeaf = true;
  int cc = 0;
  for (int ch : adj[node]) {
    if (depth[ch] > depth[node]) {
      isLeaf = false;
    } else {
      continue;
    }
    ++cc;
    int diff = abs(ch - node);
    if (diff >= len) {
      int ind = min(ch, node);
      if (s[ind] == '?') {
        ret = add(ret, solveDp(ch, 0));
        ret = add(ret, solveDp(ch, 1));
      } else {
        int u = (s[ind] - '0') ^ bit;
        ret = solveDp(ch, u);
      }
    } else {
      ret = solveDp(ch, bit);
    }
  }
  if (isLeaf) {
    ret = 1;
  }
  return ret;
}
void solve() {
  scanf(" %s ", s + 1);
  len = strlen(s + 1);
  int ret = 0;
  for (int st = 2; st <= len; ++st) {
    for (int i = 1; i <= len * 2; ++i) adj[i].clear();
    memset(dp, -1, sizeof(dp));
    memset(depth, 0, sizeof(depth));
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= len; ++i) {
      int j = len - i + 1;
      if (i != j) adj[i].push_back(j);
    }
    int g = len - st + 1;
    for (int j = st; j <= len; ++j) {
      int ind = j - st + 1;
      int nind = g - ind + 1 + (st - 1);
      if (j + len != nind + len) adj[j + len].push_back(nind + len);
    }
    for (int i = 1; i < st; ++i) {
      dp[i + len][1] = 0;
    }
    dp[1][0] = 0;
    dp[len][0] = 0;
    dp[st + len][0] = 0;
    dp[len * 2][0] = 0;
    for (int i = 1; i <= len; ++i) {
      adj[i].push_back(i + len);
      adj[i + len].push_back(i);
    }
    int tmp = 1;
    for (int i = 1; i <= len * 2; ++i) {
      assert(adj[i].size() <= 2);
      if (adj[i].size() == 1 && !vis[i]) {
        dfs(i, 0);
      }
    }
    for (int i = 1; i <= len * 2; ++i) {
      assert(vis[i]);
      if (depth[i] == 0) {
        assert(adj[i].size() == 1);
        tmp = mul(tmp, add(solveDp(i, 0), solveDp(i, 1)));
      }
    }
    ret = add(ret, tmp);
  }
  printf("%d\n", ret);
}
int main() {
  solve();
  return 0;
}