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_".
The 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.
Sometimes 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.
For example, consider a testtube with population "_babb_". There are six options for an attack that may happen next:
* the first colony attacks the second colony (1 → 2), the resulting population is "_bbbb_";
* 2 → 1, the result is "_aabb_";
* 2 → 3, the result is "_baab_";
* 3 → 2, the result is "_bbbb_" (note that the result is the same as the first option);
* 3 → 4 or 4 → 3, the population does not change.
The 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.
## Input
The first line contains an integer _n_ — the number of regions in the testtube (1 ≤ _n_ ≤ 5 000).
The second line contains _n_ small Latin letters that describe the initial population of the testtube.
## Output
Print one number — the answer to the problem modulo 109 + 7.
[samples]
## Note
In the first sample the population can never change since all bacteria are of the same type.
In 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).
To get the answer for the third sample, note that more than one attack can happen.