{"problem":{"name":"F. Bacterial Melee","description":{"content":"Julia is conducting an experiment in her lab. She placed several luminescent bacterial colonies in a horizontal testtube. Different types of bacteria can be distinguished by the color of light they em","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF760F"},"statements":[{"statement_type":"Markdown","content":"Julia is conducting an experiment in her lab. She placed several luminescent bacterial colonies in a horizontal testtube. Different types of bacteria can be distinguished by the color of light they emit. Julia marks types of bacteria with small Latin letters \"_a_\", ..., \"_z_\".\n\nThe testtube is divided into _n_ consecutive regions. Each region is occupied by a single colony of a certain bacteria type at any given moment. Hence, the population of the testtube at any moment can be described by a string of _n_ Latin characters.\n\nSometimes a colony can decide to conquer another colony in one of the adjacent regions. When that happens, the attacked colony is immediately eliminated and replaced by a colony of the same type as the attacking colony, while the attacking colony keeps its type. Note that a colony can only attack its neighbours within the boundaries of the testtube. At any moment, at most one attack can take place.\n\nFor example, consider a testtube with population \"_babb_\". There are six options for an attack that may happen next:\n\n*   the first colony attacks the second colony (1 → 2), the resulting population is \"_bbbb_\";\n*   2 → 1, the result is \"_aabb_\";\n*   2 → 3, the result is \"_baab_\";\n*   3 → 2, the result is \"_bbbb_\" (note that the result is the same as the first option);\n*   3 → 4 or 4 → 3, the population does not change.\n\nThe pattern of attacks is rather unpredictable. Julia is now wondering how many different configurations of bacteria in the testtube she can obtain after a sequence of attacks takes place (it is possible that no attacks will happen at all). Since this number can be large, find it modulo 109 + 7.\n\n## Input\n\nThe first line contains an integer _n_ — the number of regions in the testtube (1 ≤ _n_ ≤ 5 000).\n\nThe second line contains _n_ small Latin letters that describe the initial population of the testtube.\n\n## Output\n\nPrint one number — the answer to the problem modulo 109 + 7.\n\n[samples]\n\n## Note\n\nIn the first sample the population can never change since all bacteria are of the same type.\n\nIn the second sample three configurations are possible: \"_ab_\" (no attacks), \"_aa_\" (the first colony conquers the second colony), and \"_bb_\" (the second colony conquers the first colony).\n\nTo get the answer for the third sample, note that more than one attack can happen.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Julia 正在她的实验室进行一项实验。她将若干发光的细菌菌落放置在一个水平的试管中。不同类型的细菌可以通过它们发出的光的颜色来区分。Julia 用小写拉丁字母 \"_a_\" 到 \"_z_\" 标记细菌的类型。\n\n试管被划分为 #cf_span[n] 个连续的区域。在任何时刻，每个区域都由一个特定类型细菌的菌落占据。因此，试管在任何时刻的种群可以用一个由 #cf_span[n] 个拉丁字符组成的字符串描述。\n\n有时，一个菌落会决定攻击其相邻区域中的另一个菌落。当发生这种情况时，被攻击的菌落会立即被消灭，并被与攻击者相同类型的菌落取代，而攻击者保持其类型不变。注意，菌落只能攻击其在试管边界内的邻居。在任何时刻，最多只能发生一次攻击。\n\n例如，考虑一个种群为 \"_babb_\" 的试管。接下来可能发生六种攻击：\n\n攻击的模式相当不可预测。Julia 现在想知道，在一系列攻击发生后（也可能根本没有攻击），她可以获得多少种不同的细菌配置。由于这个数字可能很大，请对 #cf_span[109 + 7] 取模后输出。\n\n第一行包含一个整数 #cf_span[n] —— 试管中的区域数量（#cf_span[1 ≤ n ≤ 5 000]）。\n\n第二行包含 #cf_span[n] 个小写拉丁字母，描述试管的初始种群。\n\n请输出一个数 —— 该问题的答案对 #cf_span[109 + 7] 取模的结果。\n\n在第一个样例中，由于所有细菌类型相同，种群永远不会改变。\n\n在第二个样例中，可能有三种配置：\"_ab_\"（无攻击）、\"_aa_\"（第一个菌落征服第二个菌落）和 \"_bb_\"（第二个菌落征服第一个菌落）。\n\n对于第三个样例的答案，请注意可以发生多次攻击。\n\n## Input\n\n第一行包含一个整数 #cf_span[n] —— 试管中的区域数量（#cf_span[1 ≤ n ≤ 5 000]）。第二行包含 #cf_span[n] 个小写拉丁字母，描述试管的初始种群。\n\n## Output\n\n请输出一个数 —— 该问题的答案对 #cf_span[109 + 7] 取模的结果。\n\n[samples]\n\n## Note\n\n在第一个样例中，由于所有细菌类型相同，种群永远不会改变。在第二个样例中，可能有三种配置：\"_ab_\"（无攻击）、\"_aa_\"（第一个菌落征服第二个菌落）和 \"_bb_\"（第二个菌落征服第一个菌落）。对于第三个样例的答案，请注意可以发生多次攻击。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of regions.  \nLet $ s \\in \\{a, \\dots, z\\}^n $ be the initial string representing the bacterial population.  \n\n**Constraints**  \n$ 1 \\leq n \\leq 5000 $\n\n**Objective**  \nCompute the number of distinct strings reachable from $ s $ via any sequence of adjacent colony conquests, where an attack by a colony at position $ i $ on position $ i+1 $ (or $ i-1 $) replaces the target with the attacker’s type, modulo $ 10^9 + 7 $.  \n\n**Key Insight**  \nA configuration is reachable if and only if for each distinct character $ c $ in the final string, its occurrences form a contiguous segment, and the relative order of the leftmost occurrences of distinct characters in $ s $ is preserved.  \n\nThus, the number of reachable configurations equals the number of ways to partition the distinct characters in $ s $ (in order of first appearance) into contiguous blocks, where each block is assigned one character type, and the block boundaries respect the original left-to-right order of distinct characters.  \n\nLet $ d $ be the number of distinct characters in $ s $, and let $ c_1, c_2, \\dots, c_d $ be their order of first appearance.  \nThen the number of reachable configurations is $ 2^{d-1} $.  \n\n**Objective (Formal)**  \nLet $ d = |\\{ \\text{distinct characters in } s \\}| $.  \nCompute:  \n$$\n\\boxed{2^{d-1} \\mod (10^9 + 7)}\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF760F","tags":[],"sample_group":[["3\naaa","1"],["2\nab","3"],["4\nbabb","11"],["7\nabacaba","589"]],"created_at":"2026-03-03 11:00:39"}}