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;
constexpr int Mod = 998244353;
int Plus;
bool czy;
vector<int> dwa[2 * 1000 + 5];
vector<pair<int, int> > graf[2 * 1000 + 5];
int odw[2 * 1000 + 5], pot[2 * 1000 + 5];
bool jest[2 * 1000 + 5];
void dfs(int dom, int ind) {
  odw[dom] = ind;
  for (int i = 0; i < graf[dom].size(); ++i) {
    if (graf[dom][i].second == 0 && odw[graf[dom][i].first] == 0) {
      dfs(graf[dom][i].first, ind);
    }
  }
}
void dfs_2(int dom, int ind) {
  if (odw[dom] != 0 && odw[dom] != ind) {
    czy = 1;
  }
  if (czy == 1) {
    return;
  }
  odw[dom] = ind;
  for (int i = 0; i < dwa[dom].size(); ++i) {
    if (odw[dwa[dom][i]] != (ind ^ 1)) {
      dfs_2(dwa[dom][i], ind ^ 1);
    }
  }
}
void dfs_3(int dom) {
  odw[dom] = 1;
  for (int i = 0; i < dwa[dom].size(); ++i) {
    if (odw[dwa[dom][i]] == 0) {
      dfs_3(dwa[dom][i]);
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  string a;
  int m, wykl, wyn = 0;
  cin >> a;
  m = a.size();
  a = " " + a;
  Plus = m;
  pot[0] = 1;
  for (int i = 1; i < (2 * Plus + 2) + 1; ++i) {
    pot[i] = (pot[i - 1] * 2) % Mod;
  }
  for (int k = 1; k < m; ++k) {
    for (int j = 1; j < (2 * Plus + 2) + 1; ++j) {
      graf[j].clear();
    }
    for (int j = 1; j < k + 1; ++j) {
      if (a[j] == '1') {
        graf[j].push_back({j + Plus, 1});
        graf[j + Plus].push_back({j, 1});
      } else if (a[j] == '0') {
        graf[j].push_back({j + Plus, 0});
        graf[j + Plus].push_back({j, 0});
      }
    }
    for (int j = k + 1; j < m + 1; ++j) {
      if (a[j] == '1') {
        graf[j].push_back({2 * Plus + 1, 0});
        graf[2 * Plus + 1].push_back({j, 0});
      } else if (a[j] == '0') {
        graf[j].push_back({2 * Plus + 2, 0});
        graf[2 * Plus + 2].push_back({j, 0});
      }
    }
    for (int j = 1; j < k / 2 + 1; ++j) {
      graf[j + Plus].push_back({k - j + Plus + 1, 0});
      graf[k - j + Plus + 1].push_back({j + Plus, 0});
    }
    for (int j = 1; j < m / 2 + 1; ++j) {
      graf[j].push_back({m - j + 1, 0});
      graf[m - j + 1].push_back({j, 0});
    }
    graf[2 * Plus + 1].push_back({m + k, 0});
    graf[m + k].push_back({2 * Plus + 1, 0});
    graf[2 * Plus + 1].push_back({2 * Plus + 2, 1});
    graf[2 * Plus + 2].push_back({2 * Plus + 1, 1});
    fill(odw + 1, odw + (2 * Plus + 2) + 1, 0);
    fill(jest + 1, jest + (2 * Plus + 2) + 1, 0);
    for (int j = 1; j < (2 * Plus + 2) + 1; ++j) {
      if (odw[j] == 0) {
        dfs(j, j);
        jest[j] = 1;
      }
    }
    for (int j = 1; j < (2 * Plus + 2) + 1; ++j) {
      dwa[j].clear();
    }
    for (int j = 1; j < (2 * Plus + 2) + 1; ++j) {
      for (int l = 0; l < graf[j].size(); ++l) {
        if (graf[j][l].second == 1) {
          dwa[odw[j]].push_back(odw[graf[j][l].first]);
        }
      }
    }
    czy = 0;
    fill(odw + 1, odw + (2 * Plus + 2) + 1, 0);
    for (int j = 1; j < (2 * Plus + 2) + 1; ++j) {
      if (odw[j] == 0) {
        dfs_2(j, 2);
      }
    }
    if (czy == 0) {
      wykl = 0;
      fill(odw + 1, odw + (2 * Plus + 2) + 1, 0);
      for (int j = 1; j < (2 * Plus + 2) + 1; ++j) {
        if (odw[j] == 0 &&
            (j <= m + k || j == (2 * Plus + 2) || j == (2 * Plus + 1)) &&
            jest[j] == 1) {
          dfs_3(j);
          wykl++;
        }
      }
      wyn += pot[wykl - 1];
      wyn %= Mod;
    }
  }
  cout << wyn << "\n";
  return 0;
}