{"problem":{"name":"G. Palindrome Partition","description":{"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","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF932G"},"statements":[{"statement_type":"Markdown","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.\n\n## Input\n\nThe only line of input contains a string _s_ (2 ≤ |_s_| ≤ 106) of even length consisting of lowercase Latin letters.\n\n## Output\n\nPrint one integer, the number of ways of partitioning the string modulo 109 + 7.\n\n[samples]\n\n## Note\n\nIn 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_.","is_translate":false,"language":"English"},{"statement_type":"Markdown","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]。\n\n## Input\n\n输入仅一行，包含一个长度为偶数的字符串 #cf_span[s] #cf_span[(2 ≤ |s| ≤ 106)]，由小写拉丁字母组成。\n\n## Output\n\n请输出一个整数，表示将字符串分割的方案数对 #cf_span[109 + 7] 取模的结果。\n\n[samples]\n\n## Note\n\n在第一个例子中，分割字符串的唯一方式是 #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]。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**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 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF932G","tags":["dp","string suffix structures","strings"],"sample_group":[["abcdcdab","1"],["abbababababbab","3"]],"created_at":"2026-03-03 11:00:39"}}