{"raw_statement":[{"iden":"statement","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."},{"iden":"input","content":"The 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."},{"iden":"output","content":"Print one number — the answer to the problem modulo 109 + 7."},{"iden":"examples","content":"Input\n\n3\naaa\n\nOutput\n\n1\n\nInput\n\n2\nab\n\nOutput\n\n3\n\nInput\n\n4\nbabb\n\nOutput\n\n11\n\nInput\n\n7\nabacaba\n\nOutput\n\n589"},{"iden":"note","content":"In 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."}],"translated_statement":[{"iden":"statement","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对于第三个样例的答案，请注意可以发生多次攻击。"},{"iden":"input","content":"第一行包含一个整数 #cf_span[n] —— 试管中的区域数量（#cf_span[1 ≤ n ≤ 5 000]）。第二行包含 #cf_span[n] 个小写拉丁字母，描述试管的初始种群。"},{"iden":"output","content":"请输出一个数 —— 该问题的答案，对 #cf_span[109 + 7] 取模。"},{"iden":"examples","content":"输入3aaa输出1输入2ab输出3输入4babb输出11输入7abacaba输出589"},{"iden":"note","content":"在第一个样例中，由于所有细菌类型相同，种群永远不会改变。在第二个样例中，有三种可能的配置：\"_ab_\"（无攻击）、\"_aa_\"（第一个菌落征服第二个菌落）和 \"_bb_\"（第二个菌落征服第一个菌落）。对于第三个样例的答案，请注意可以发生多次攻击。"}],"sample_group":[],"show_order":[],"formal_statement":"**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 reachable configurations of the string under the following rules:  \n- At most one attack occurs at a time.  \n- An attack: a colony at position $ i $ (with character $ c $) conquers an adjacent colony at $ i+1 $ or $ i-1 $, replacing it with $ c $.  \n- The attacking colony remains unchanged.  \n- Attacks may occur in any sequence, including zero.  \n\nThe answer is the size of the set of all strings reachable from $ s $ via any sequence of such attacks, modulo $ 10^9 + 7 $.","simple_statement":null,"has_page_source":false}