Killjee can't even think of a cakewalk, so, he made a hard problem for you guys. There are n persons in a room. Every person has a single character unique name. There is a string containing names of people. It is guaranteed that name of every person is in the string.

You need to find in how many ways all the persons can be arranged in a straight line.

Note: A person's name can be there in the string more than 1 time too.

INPUT

First line of input contain a single integer n denoting length of string s

Second line of Input contain string s.

OUTPUT

Output answer to the question % $10^9+7$.

** CONSTRAINTS**

$1 \le |s| \le 10^{6}$