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 const char * tme = __TIME__;
static_assert(tme[6] != '0' && tme[7] != '0', "Error!");

typedef long long ll;
const int mod = 998244353;
inline ll modpower(ll x, ll y) {
	ll res = 1;
	while (y) {
		if (y & 1) (res *= x) %= mod;
		(x *= x) %= mod, y >>= 1;
	}
	return res;
}

string str;
int n;
vector <pair <int, int> > g[2005];
// 0: same, 1: diff
// a: [0, n), b: [n, 2*n)

int vis[2005];
int col[2005];
int conflict;
void dfs(int u, int c) {
	if (vis[u]) {
		if (col[u] != c)
			conflict = 1;
		return ;
	}
	vis[u] = 1;
	col[u] = c;
	for (auto &pr: g[u]) {
		int v = pr.first, cl = pr.second;
		dfs(v, c ^ cl);
	}
}

ll calc(int len) {
	for (int i = 0; i < n * 2 + 2; ++ i) g[i].clear();
	int zero = n * 2, one = n * 2 + 1;
	for (int i = 0; i < n; ++ i) // a palindrome
		g[i].push_back({n - i - 1, 0});
	for (int i = 0; i < len; ++ i) // b palindrome
		g[i + n].push_back({len - i - 1 + n, 0}); 
	for (int i = len; i < n; ++ i) { // no
		g[i + n].push_back({zero, 0});
		g[zero].push_back({i + n, 0});
	}
	for (int i = 0; i < n; ++ i)
		if (str[n - i - 1] == '0') {
			g[i].push_back({i + n, 0});
			g[i + n].push_back({i, 0});
		}
		else if (str[n - i - 1] == '1') {
			g[i].push_back({i + n, 1});
			g[i + n].push_back({i, 1});
		}
	g[0].push_back({zero, 1});
	g[n].push_back({zero, 1});
	g[zero].push_back({0, 1});
	g[zero].push_back({n, 1});
	g[zero].push_back({one, 1});
	g[one].push_back({zero, 1});
	memset(vis, 0, sizeof vis);
	memset(col, -1, sizeof col);
	int cnt = 0;
	conflict = 0;
	for (int i = 0; i < n * 2 + 2; ++ i)
		if (!vis[i]) {
			dfs(i, 0);
			cnt ++;
		}
	if (conflict) return 0;
	return modpower(2, cnt - 1);
}

int main() {
	cin >> str ;
	n = str.length();
	ll ans = 0;
	for (int i = 1; i < n; ++ i) {
		ll now = calc(i);
		(ans += now) %= mod;
	}
	printf("%lld\n", ans);
	return 0;
}