Little D and Little H are two geniuses. They often play games that only geniuses would play, such as "mentally calculating whether a 4-digit number is a perfect square."

Today, they discovered a new game: First, a prefix of $s$ of length $\rm len$ is called a border if and only if $s[1\dots \text {len} ] = s[|s|-\text {len} + 1\dots |s|]$. Given a string $s$ consisting of 0, 1, and ?, replace the question marks in $s$ with 0 or 1. For each $\rm len$, determine if there exists a way to replace the question marks such that the prefix of $s$ of length $\rm len$ becomes a border. Let this result be $f(\text{len}) \in \{0, 1\}$. $f(\text{len}) = 1$ if the prefix of $s$ of length $\rm len$ can be a border, otherwise $f(\text{len}) = 0$.

Since Little D and Little H are geniuses, the length of $s$ they calculate is very long, so comparing the results one by one would take a long time. For convenience, they defined a checksum: $(f(1)\times 1^2)~\text{xor}~(f(2)\times 2^2)~\text{xor}~(f(3)\times 3^2)~\text{xor}~\dots~\text{xor}~(f(n)\times n^2)$ to verify if their answers are the same. Here, xor denotes the bitwise exclusive OR operation. Unfortunately, in one game, their calculated checksums were different, and they would like you to help them calculate the correct checksum. Of course, they do not force you to calculate it mentally; you can solve it by programming.

Input

A string $s$, where each character is guaranteed to be 0, 1, or ?.

Output

Output the checksum of the string, i.e., $(f(1)\times 1^2)~\text{xor}~(f(2)\times 2^2)~\text{xor}~(f(3)\times 3^2)~\text{xor}~\dots~\text{xor}~(f(n)\times n^2)$.

Examples

Input 1

1?0?

Output 1

17

Note 1

If we fill the question marks to get 1001, the string has a border of length 1, so $f(1) = 1$.

If we fill the question marks to get 1101, the string has a border of length 4, so $f(4) = 1$.

For $f(2)$ and $f(3)$, one can enumerate all possible fillings to prove their values are 0.

Therefore, the answer is $1^2~\text{xor}~4^2=17$.

Subtasks

This problem uses bundled testing. We divide the test cases into several subtasks. For a subtask, you can only receive the points for that subtask if you pass all test cases within it. The constraints for each subtask are as follows: