题目描述

小 D 和小 H 是两位神仙。他们经常在一起玩神仙才会玩的一些游戏，比如「口算一个 $4$ 位数是不是完全平方数」。

今天他们发现了一种新的游戏：首先称 $s$ 长度为 $\rm len$ 的前缀成为 border 当且仅当 $s[1\dots \text {len} ] = s[|s|-\text {len} + 1\dots |s|]$ 。给出一个由 01? 组成的字符串 $s$, 将 $s$ 中的问号用变成 01 替换，对每个 $\rm len$ 口算是否存在替换问号的方案使得 $s$ 长度为 $\rm len$ 的前缀成为 border，把这个结果记做 $f(\text{len})\in {0,1}$。$f(\text{len}) = 1$ 如果 $s$ 长度为 $\rm len$ 的前缀能够成为 border，否则 $f(\text{len}) = 0$。

由于小 D 和小 H 是神仙，所以他们计算的 $s$ 的长度很长，因此把计算的结果一一比对会花费很长的时间。为了方便比对，他们规定了一个校验值：$(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)$ 来校验他们的答案是否相同。xor 表示按位异或。但是不巧，在某一次游戏中，他们口算出的校验值并不一样，他们希望你帮助他们来计算一个正确的校验值。当然，他们不强迫你口算，可以编程解决。

输入格式

一个串 $s$, 保证每个字符都是 0，1，或者?.

输出格式

输出字符串的校验值， 即 $(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)$。

样例

input

1?0?

output

17

将问号填充为 1001，则这个串有长度为 $1$ 的 border, 故 $f(1) = 1$。

将问号填充为 1101，则这个串有长度为 $4$ 的 border, 故 $f(4) = 1$。

对于 $f(2)$ 和 $f(3)$，可以枚举填充的字符是什么来证明他们的值是 0。

故答案是$1^2~\text{xor}~4^2=17$

数据范围与提示

本题采用捆绑测试，我们将测试点分成若干个 subtask，对于一个 subtask，只有通过这个 subtask 的所有测试点才能拿到这个 subtask 的分数。每个 subtask 的限制如下：