{"raw_statement":[{"iden":"statement","content":"Given a string _s_, find the number of ways to split _s_ to substrings such that if there are _k_ substrings (_p_1, _p_2, _p_3, ..., _p__k_) in partition, then _p__i_ = _p__k_ - _i_ + 1 for all _i_ (1 ≤ _i_ ≤ _k_) and _k_ is even.\n\nSince the number of ways can be large, print it modulo 109 + 7."},{"iden":"input","content":"The only line of input contains a string _s_ (2 ≤ |_s_| ≤ 106) of even length consisting of lowercase Latin letters."},{"iden":"output","content":"Print one integer, the number of ways of partitioning the string modulo 109 + 7."},{"iden":"examples","content":"Input\n\nabcdcdab\n\nOutput\n\n1\n\nInput\n\nabbababababbab\n\nOutput\n\n3"},{"iden":"note","content":"In the first case, the only way to partition the string is _ab_|_cd_|_cd_|_ab_.\n\nIn the second case, the string can be partitioned as _ab_|_b_|_ab_|_ab_|_ab_|_ab_|_b_|_ab_ or _ab_|_b_|_abab_|_abab_|_b_|_ab_ or _abbab_|_ab_|_ab_|_abbab_."}],"translated_statement":[{"iden":"statement","content":"给定一个字符串 #cf_span[s]，求将 #cf_span[s] 分割为若干子串的方案数，使得若分割后有 #cf_span[k] 个子串 #cf_span[(p1, p2, p3, ..., pk)]，则对所有 #cf_span[i] #cf_span[(1 ≤ i ≤ k)] 都满足 #cf_span[pi = pk - i + 1]，且 #cf_span[k] 为偶数。\n\n由于方案数可能很大，请对 #cf_span[109 + 7] 取模输出。\n\n输入仅一行，包含一个长度为偶数的字符串 #cf_span[s] #cf_span[(2 ≤ |s| ≤ 106)]，由小写拉丁字母组成。\n\n请输出一个整数，表示将字符串分割的方案数对 #cf_span[109 + 7] 取模的结果。\n\n在第一个例子中，分割字符串的唯一方式是 #cf_span[ab|cd|cd|ab]。\n\n在第二个例子中，字符串可以被分割为 #cf_span[ab|b|ab|ab|ab|ab|b|ab] 或 #cf_span[ab|b|abab|abab|b|ab] 或 #cf_span[abbab|ab|ab|abbab]。"},{"iden":"input","content":"输入仅一行，包含一个长度为偶数的字符串 #cf_span[s] #cf_span[(2 ≤ |s| ≤ 106)]，由小写拉丁字母组成。"},{"iden":"output","content":"请输出一个整数，表示将字符串分割的方案数对 #cf_span[109 + 7] 取模的结果。"},{"iden":"examples","content":"输入\nabcdcdab\n输出\n1\n输入\nabbababababbab\n输出\n3"},{"iden":"note","content":"在第一个例子中，分割字符串的唯一方式是 #cf_span[ab|cd|cd|ab]。在第二个例子中，字符串可以被分割为 #cf_span[ab|b|ab|ab|ab|ab|b|ab] 或 #cf_span[ab|b|abab|abab|b|ab] 或 #cf_span[abbab|ab|ab|abbab]。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ s \\in \\Sigma^* $ be a string of even length $ n = |s| $, where $ \\Sigma $ is the set of lowercase Latin letters.  \nLet $ k \\in 2\\mathbb{Z}^+ $ be an even positive integer.  \nA partition of $ s $ into $ k $ non-empty contiguous substrings $ (p_1, p_2, \\dots, p_k) $ is called *palindromic-symmetric* if $ p_i = p_{k - i + 1} $ for all $ i \\in \\{1, 2, \\dots, k\\} $.\n\n**Constraints**  \n1. $ 2 \\leq n \\leq 10^6 $  \n2. $ n $ is even.  \n3. Each substring $ p_i $ is non-empty and contiguous.  \n4. The partition must satisfy $ p_i = p_{k - i + 1} $ for all $ i $, and $ k $ is even.\n\n**Objective**  \nCount the number of palindromic-symmetric partitions of $ s $, modulo $ 10^9 + 7 $.","simple_statement":null,"has_page_source":false}