매직

다스칼로프 선생님의 9학년 영어 수업 시간이다. 주인공 데니는 영어가 약해서 교실 안을 날아다니는 파리 수를 세고 있다. 그것마저 지루해지자 데니는 선생님이 칠판에 적어 둔 글로 눈을 돌린다. 단어 사이의 공백을 무시하면 칠판의 글은 데니에게 길이가 $N$인 영어 알파벳 한 줄로 보인다. 이 문자열에 나오는 서로 다른 문자의 개수를 $K$라고 하자. 데니는 문자열에서 부분 문자열을 하나씩 골라 각 문자가 몇 번 나오는지 적는다. $K$개 문자의 등장 횟수가 모두 같으면 데니는 그 부분 문자열을 마법 부분 문자열이라고 부른다.

부분 문자열은 문자열에서 연속한 문자만 잘라낸 조각이다.

이 수업 시간에 데니는 문자열의 모든 부분 문자열을 확인해서 마법 부분 문자열이 몇 개인지 셌고, 다 세고 나자 아주 뿌듯해했다. 데니는 영어 수업마다 이렇게 하기로 마음먹는다. 그런데 수업이 거듭될수록 다스칼로프 선생님이 칠판에 적는 글은 점점 길어진다. 그래서 데니가 도움을 청했다. 영어 알파벳 $N$개로 이루어진 문자열이 주어지면 마법 부분 문자열의 개수를 세는 프로그램을 작성하라. 내용이 같아도 위치가 다르면 서로 다른 부분 문자열로 센다.

첫째 줄에 다스칼로프 선생님이 적은 문자열의 길이 $N$이 주어진다. 둘째 줄에 영어 알파벳 $N$개로 이루어진 문자열이 주어진다. 대문자와 소문자가 모두 나올 수 있고, 같은 글자라도 대소문자가 다르면 서로 다른 문자다(A와 a는 다른 문자다).

첫째 줄에 주어진 문자열의 마법 부분 문자열 개수를 출력한다. 이 값이 매우 클 수 있으므로 1,000,000,007로 나눈 나머지를 출력한다.

• $2 \le N \le 100\,000$

첫 번째 예제에서 마법 부분 문자열은 abc, cba, abc, abccba이다. 예를 들어 ab는 문자 c가 들어 있지 않으므로 마법 부분 문자열이 아니다.

두 번째 예제에서 마법 부분 문자열은 abcABC 하나뿐이다. a는 소문자이고 A는 대문자이므로 둘은 다른 문자다.

세 번째 예제의 답은 22이고, 그중 하나가 SwSwwS이다.