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;
struct InputReader {
  char buf[1000001];
  int p;
  inline InputReader() { p = 1000001; }
  inline void Flush() {
    p = 0;
    fread(buf, 1, 1000001, stdin);
  }
  inline char C() {
    if (p >= 1000001) Flush();
    return buf[p++];
  }
  inline char Readnum() {
    char ch = C();
    while (!isdigit(ch) && ch != '-') ch = C();
    return ch;
  }
  inline void Readalpha(char &c) {
    c = C();
    while (!isalpha(c)) c = C();
  }
  int operator()() {
    int ans = 0, fu = 1;
    char ch = Readnum();
    if (ch == '-') fu = -1, ch = C();
    while (ch >= '0' && ch <= '9') {
      ans = ans * 10 + ch - '0';
      ch = C();
    }
    return ans * fu;
  }
  long long Readll() {
    long long ans = 0LL, fu = 1LL;
    char ch = Readnum();
    if (ch == '-') fu = -1LL, ch = C();
    while (ch >= '0' && ch <= '9') {
      ans = ans * 10LL + ch - '0';
      ch = C();
    }
    return ans * fu;
  }
  inline void Readstring(string &x) {
    x.clear();
    char ch = C();
    while (!isdigit(ch) && !isalpha(ch) && ch != '?' && ch != '.') ch = C();
    while (isdigit(ch) || isalpha(ch) || ch == '?' || ch == '.') {
      x += ch;
      ch = C();
    }
  }
  inline void Readchstring(char s[]) {
    int len = 0;
    char ch = C();
    while (!isdigit(ch) && !isalpha(ch)) ch = C();
    while (isdigit(ch) || isalpha(ch)) {
      s[len++] = ch;
      ch = C();
    }
    s[len] = '\0';
  }
  inline void Specialread(char &c) {
    c = C();
    while (!isdigit(c) && !isalpha(c) && c != '#' && c != '.' && c != '=' &&
           c != 'B')
      c = C();
  }
} In;
inline void Read(int &x) { x = In(); }
inline void Read(int &x, int &y) {
  x = In();
  y = In();
}
inline void Read(int &x1, int &x2, int &x3) {
  x1 = In();
  x2 = In();
  x3 = In();
}
inline void Read(int &x1, int &x2, int &x3, int &x4) {
  x1 = In();
  x2 = In();
  x3 = In();
  x4 = In();
}
inline void Read(long long &x) { x = In.Readll(); }
inline void Read(long long &x, long long &y) {
  x = In.Readll();
  y = In.Readll();
}
inline void Read(long long &x1, long long &x2, long long &x3) {
  x1 = In.Readll();
  x2 = In.Readll();
  x3 = In.Readll();
}
inline void Read(long long &x1, long long &x2, long long &x3, long long &x4) {
  x1 = In.Readll();
  x2 = In.Readll();
  x3 = In.Readll();
  x4 = In.Readll();
}
template <typename T>
void Read(T a[], int st, int ed) {
  for (int(i) = (st); (i) <= (ed); ++(i)) Read(a[i]);
}
inline void FILEIO() {}
inline void FILEIO(string pname) {
  freopen((pname + ".in").c_str(), "r", stdin);
  freopen((pname + ".out").c_str(), "w", stdout);
}
inline void FILEIO_OICONTEST(string pname) {
  freopen((pname + ".in").c_str(), "r", stdin);
  freopen((pname + ".out").c_str(), "w", stdout);
}
void Printtime() {}
void END() {
  Printtime();
  exit(0);
}
template <typename T>
void END(T mes) {
  cout << mes << endl;
  END();
}
template <typename T>
void Print(T a[], int s, int t, char sp = ' ', char ed = '\n') {
  if (s > t) return;
  for (int i = s; i < t; i++) cout << a[i] << sp;
  cout << a[t] << ed;
  cout.flush();
}
template <typename T>
void Print(T a, int s = 0, int t = -1, char sp = ' ', char ed = '\n') {
  if (t == -1) t = a.size() - 1;
  for (int i = s; i <= t; i++) cout << a[i] << sp;
  cout << ed;
  cout.flush();
}
long long Pow(long long a, long long b, long long p = (998244353LL)) {
  long long ret = 1;
  for (; b; a = a * a % p, b >>= 1LL)
    if (b & 1LL) ret = ret * a % p;
  return ret;
}
long long Inv(long long a, long long p = (998244353LL)) {
  return Pow(a, p - 2LL, p);
}
struct Edge {
  int to, type;
};
int n;
string s;
vector<Edge> e[2048];
vector<int> available;
void Clear() {
  for (int(i) = 0; (i) < (2048); ++(i)) e[i].clear();
  available.clear();
}
void BuildGraph(int k) {
  for (int(i) = 1; (i) <= (n); ++(i)) available.push_back(i);
  for (int(i) = 1; (i) <= (k); ++(i)) available.push_back(n - k + i + n);
  available.push_back(2044);
  available.push_back(2045);
  for (int(i) = 1; (i) <= (n); ++(i))
    if (i != n - i + 1) e[i].push_back({n - i + 1, 0});
  for (int(i) = 1; (i) <= (k); ++(i)) {
    int u = n - k + i;
    int v = n - i + 1;
    if (u != v) e[u + n].push_back({v + n, 0});
  }
  for (int(i) = 1; (i) <= (n - k); ++(i)) {
    if (s[i] == '0') {
      e[2044].push_back({i, 0});
      e[i].push_back({2044, 0});
    } else if (s[i] == '1') {
      e[2045].push_back({i, 0});
      e[i].push_back({2045, 0});
    }
  }
  for (int(i) = (n - k + 1); (i) <= (n); ++(i)) {
    if (s[i] == '0') {
      e[i].push_back({i + n, 0});
      e[i + n].push_back({i, 0});
    } else if (s[i] == '1') {
      e[i].push_back({i + n, 1});
      e[i + n].push_back({i, 1});
    }
  }
  e[2044].push_back({2045, 1});
  e[2045].push_back({2044, 1});
  int u = n - k + 1;
  e[u + n].push_back({2045, 0});
  e[2045].push_back({u + n, 0});
  u = 1;
  e[u].push_back({2045, 0});
  e[2045].push_back({u, 0});
}
int col[2048];
bool Dfs(int pos, int ucol) {
  col[pos] = ucol;
  for (auto [v, tp] : e[pos]) {
    if (col[v] != 0) {
      if (tp == 0 and col[v] != col[pos]) return 1;
      if (tp == 1 and col[v] == col[pos]) return 1;
      continue;
    }
    if (tp == 0 and Dfs(v, ucol)) return 1;
    if (tp == 1 and Dfs(v, ucol * (-1))) return 1;
  }
  return 0;
}
int Check() {
  memset(col, 0, sizeof(col));
  int cnt = 0;
  for (auto p : available) {
    if (col[p] != 0) continue;
    if (Dfs(p, 1)) return 0;
    ++cnt;
  }
  return cnt;
}
long long Try(int k) {
  Clear();
  BuildGraph(k);
  int component = Check();
  if (!component) return 0;
  long long ans = Pow(2, component - 1);
  return ans;
}
int main() {
  FILEIO();
  In.Readstring(s);
  n = s.length();
  s = " " + s;
  long long ans = 0;
  for (int(i) = 1; (i) <= (n - 1); ++(i)) {
    long long tans = Try(i);
    ans += tans;
    ans = (ans) >= (998244353LL) ? ((ans) - (998244353LL)) : (ans);
  }
  cout << ans << endl;
  END();
}