{"problem":{"name":"D. 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":"CF756D"},"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"}],"meta":{"iden":"CF756D","tags":["brute force","combinatorics","dp","string suffix structures"],"sample_group":[["3\naaa","1"],["2\nab","3"],["4\nbabb","11"],["7\nabacaba","589"]],"created_at":"2026-03-03 11:00:39"}}