#340. 本质不同子串个数

题目类型:传统型 时间限制:5000 ms 空间限制:512 MiB
输入文件:标准输入 输出文件:标准输出 答案检查器:文本比较

给定字符串,对于每个前缀计算其本质不同子串个数。输出所有答案的异或。


input

一行一个字符串。

output

一个整数表示答案(注意可能超过int范围)。


sample input 1

aab

sample output 1

6

sample input 2

cslnbcslcsl

sample output 2

44

constraints

$1 \le |s| \le 5000000$,保证字符是小写字母。

子任务$1$($1\texttt{pts}$):$1 \le |s| \le 100$

子任务$2$($49\texttt{pts}$):$1 \le |s| \le 100000$

子任务$3$($49\texttt{pts}$):$1 \le |s| \le 1000000$

子任务$4$($1\texttt{pts}$):无特殊限制


by $\textbf{fizzydavid}$