【 Description 】
小C班上的语文课代表。他常常在作文里使用各种形如“ABAB”的四字词语。诸如“碧蓝碧蓝”“锻炼锻炼”“琢磨琢磨”“彼此彼此”，都是他平日写作文时的最爱。现在，他的眼前飘过了一串字符序列。他想知道其中会有多少个形如“ABAB”的子序列，你能告诉他吗？
具体地，你会得到一个长度为 N 的字符序列S。方便起见，我们用0, 1, 2, …, N - 1为 S 中的每一位字符依次编号，并用Si表示S中编号为i的字符。你的任务是找出所有的整数四元组 (i, j, k, l)，满足 0 ≤ i < j < k < l < N 且 Si = Sk、Sj = Sl、Si ≠ Sj。
【 Input 】
第一行为一个整数N，表示字符序列的长度。
第二行为一个长度N的字符串，字符串仅包含大写字母，表示给定的字符序列。
【 Output 】
一个整数，表示给定的字符序列中有多少个形如“ABAB”的子序列。
答案可能很大，请输出对109 + 7取模之后的结果。
【HINT】
【样例说明1】
如下所示，满足要求的子序列包括2个ACAC、2个BCBC、2个CACA。
ABCBCACA
ABCBCACA
ABCBCACA
ABCBCACA
ABCBCACA
ABCBCACA
【样例输入2】
20
SSSSTTTTSSSSTTTTSSSS
【样例输出2】
512
【样例说明2】
满足要求的子序列包括256个STST和256个TSTS。
【数据规模与约定】
对于25%的测试点，保证1 ≤ N ≤ 100。
对于50%的测试点，保证1 ≤ N ≤ 1000。
另有15%的测试点，保证S中仅包含2个不同的字符。
对于100%的测试点，保证1 ≤ N ≤ 1000000。
