Border Game Checksum

Given a string s consisting of characters from the set {0, 1, ?}, you are allowed to replace every ? with either 0 or 1 arbitrarily. For every integer l with 1 ≤ l ≤ |s|, consider whether there exists a substitution of the question marks such that the prefix of s of length l becomes a border of the string.

A prefix of s of length l is called a border if it is equal to the suffix of s of length l. In other words, if we denote the string positions starting from 1 and let
$$\textbf{s}[1\dots l] = \textbf{s}[|s|-l+1\dots |s|],$$ then the prefix is a border.

Define a function \(f(l)\) such that:

$$f(l)=\begin{cases}1,&\text{if there exists a valid substitution making the prefix of length }l\text{ a border},\\ 0,&\text{otherwise}.\end{cases} $$

Your task is to compute the following checksum:

$$\text{checksum} = \bigoplus_{l=1}^{|s|} f(l) \times l^2, $$

where \(\oplus\) denotes the bitwise XOR operation. Output the checksum.

inputFormat

The input consists of a single line containing a string s consisting only of the characters 0, 1, and ?.

outputFormat

Output a single integer representing the computed checksum.

sample

1?0

13