Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

D. Palindrome XOR

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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)$$$.

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/23/2020 09:09:39 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|