D. Palindrome XOR
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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 \leq 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 \leq |s| \leq 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)$$$.