题目描述

给你一个字符串，求所有长度为偶数的前缀在整个字符串出现的次数和。

输入

共一行，一个字符串$s$。

输出

共一行，输出一个整数,代表长度为偶数的前缀在整个字符串出现的次数和。

输入样例

abababc

输出样例

6

提示

【输入样例2】

isdashagayisdashagaydashisnotagaydashisnotagay

【输出样例2】

30

【数据规模】 对于30%的数据，|S| <= 100，保证数据随机。 对于100%的数据，|S| <= 200000。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共9个测试点，非原站或官方原始数据。总分100分。