{"raw_statement":[{"iden":"statement","content":"String _s_ of length _n_ is called _k_\\-palindrome, if it is a palindrome itself, and its prefix and suffix of length are (_k_ - 1)\\-palindromes. By definition, any string (even empty) is 0-palindrome.\n\nLet's call the palindrome degree of string _s_ such a maximum number _k_, for which _s_ is _k_\\-palindrome. For example, \"_abaaba_\" has degree equals to 3.\n\nYou are given a string. Your task is to find the sum of the palindrome degrees of all its prefixes."},{"iden":"input","content":"The first line of the input data contains a non-empty string, consisting of Latin letters and digits. The length of the string does not exceed 5·106. The string is case-sensitive."},{"iden":"output","content":"Output the only number — the sum of the polindrome degrees of all the string's prefixes."},{"iden":"examples","content":"Input\n\na2A\n\nOutput\n\n1\n\nInput\n\nabacaba\n\nOutput\n\n6"}],"translated_statement":[{"iden":"statement","content":"长度为 #cf_span[n] 的字符串 #cf_span[s] 被称为 #cf_span[k]-回文串，当且仅当它本身是回文串，且其长度为 #cf_span[(k - 1)] 的前缀和后缀都是 #cf_span[(k - 1)]-回文串。根据定义，任意字符串（包括空字符串）都是 0-回文串。\n\n我们定义字符串 #cf_span[s] 的回文度为最大的数 #cf_span[k]，使得 #cf_span[s] 是 #cf_span[k]-回文串。例如，\"_abaaba_\" 的回文度为 #cf_span[3]。\n\n给你一个字符串，你的任务是求出它的所有前缀的回文度之和。\n\n输入数据的第一行包含一个非空字符串，由拉丁字母和数字组成。字符串长度不超过 #cf_span[5·106]。字符串区分大小写。\n\n请输出一个数——该字符串所有前缀的回文度之和。"},{"iden":"input","content":"输入数据的第一行包含一个非空字符串，由拉丁字母和数字组成。字符串长度不超过 #cf_span[5·106]。字符串区分大小写。"},{"iden":"output","content":"请输出一个数——该字符串所有前缀的回文度之和。"},{"iden":"examples","content":"输入\na2A\n输出\n1\n\n输入\nabacaba\n输出\n6"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ s $ be a string of length $ n $.  \nFor $ k \\in \\mathbb{N}_0 $, define that $ s $ is a **$ k $-palindrome** if:  \n- $ k = 0 $: always true (by definition),  \n- $ k \\geq 1 $: $ s $ is a palindrome **and** its prefix (and suffix) of length $ \\lfloor |s|/2 \\rfloor $ is a $ (k-1) $-palindrome.  \n\nLet $ d(s) $ denote the **palindrome degree** of string $ s $: the maximum $ k $ such that $ s $ is a $ k $-palindrome.\n\n**Constraints**  \n- $ 1 \\leq |s| \\leq 5 \\cdot 10^6 $  \n- $ s $ consists of Latin letters and digits (case-sensitive)  \n\n**Objective**  \nCompute:  \n$$\n\\sum_{i=1}^{n} d(s[1:i])\n$$  \nwhere $ s[1:i] $ denotes the prefix of $ s $ of length $ i $.","simple_statement":null,"has_page_source":false}