Description

Little D and Little H are two immortals. They often play games that only immortals would play, such as “mentally checking whether a 4-digit number is a perfect square”.

Today they found a new game: first, for a string $s$, a prefix of length $len$ is called a border if and only if $s[1\dots len] = s[|s|-len+1\dots |s|]$. Given a string $s$ consisting of $\texttt{01?}$, replace each question mark in $s$ with $\texttt{0}$ or $\texttt{1}$. For each $len$, mentally determine whether there exists a way to replace the question marks such that the prefix of $s$ of length $len$ becomes a border, and record this result as $f(len)\in\{0,1\}$. If the prefix of $s$ of length $len$ can become a border, then $f(len)=1$; otherwise $f(len)=0$.

Since Little D and Little H are immortals, the length of $s$ they compute is very large, so comparing the results one by one would take a long time. To make comparison easier, they define a checksum: $(f(1)\times 1^2)~\operatorname{xor}~(f(2)\times 2^2)~\operatorname{xor}~(f(3)\times 3^2)~\operatorname{xor}~\dots~\operatorname{xor}~(f(n)\times n^2)$ to verify whether their answers are the same. $\operatorname{xor}$ denotes bitwise XOR. Unfortunately, in one game, the checksums they computed mentally were not the same. They want you to help them compute the correct checksum. Of course, they do not force you to do it mentally; you may solve it by programming.

Input Format

A string $s$, guaranteed that each character is $\texttt 0$, $\texttt 1$, or $\texttt ?$.

Output Format

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

1?0?

17

Hint

Sample Explanation

Fill the question marks as 1001. Then this string has a border of length 1, so $f(1)=1$.

Fill the question marks as 1101. Then this string has a border of length 4, so $f(4)=1$.

For $f(2)$ and $f(3)$, you can enumerate what characters are filled in to prove that their values are 0.

So the answer is $1^2~\operatorname{xor}~4^2=17$.

Constraints

Translated by ChatGPT 5