曾经沧海难为水

【题目描述】
远远的海面上，时不时一个滔天巨浪泛起，犹如平地起了一座巍峨高墙，随即崩溃倾塌。还有水龙一般道道水柱，冲天而起，如龙卷风一般肆虐发狂，起来又倒下。天边爬过森森苍雷，扭曲而狰狞。
...
再睁眼时，小 L 发觉自己身处一片海滩。海滩之外，便是广袤无垠、无边无际的大海。之所以海滩是灰的，并非是因为沙是灰的，而是因为天空是灰色的，海也是灰色的。乌压乌压，黑云滚滚，沉沉的甚是压抑，令人喘不过气。
在这片灰色的沙滩上，引人注目的唯一色彩便是沙砾中半掩着的贝壳。这些贝壳只有红、白两种颜色。
“咳咳... 要我说，这红色的贝壳要和白色的贝壳间隔着放才好看。”
“嗯，每个哥哥的身边都要有一个小 H 陪伴着。”
“......”
现在海滩上共有 \(n\) 个贝壳，它们排成了一行。
小 L 喜欢的贝壳序列具有一个性质：从第二个贝壳开始的每个贝壳，都与它之前的一个贝壳颜色不同如：红、白、红、白、红就是小 L 喜欢的序列，而白、红、红就不是。
现在小 H 想要从这 \(n\) 个贝壳当中选出一个非空的小 L 喜欢的子序列（不需要连续），即在这个贝壳的子序列当中相邻的两个贝壳的颜色是不同的。
注意，在选出的子序列中，第一个贝壳的颜色既可以是红色也可以是白色的。
由于这个答案可能会很大，你只需要输出它对 \(10^9 + 7\) 取模后的结果。
【输入格式】
一行一个数$ n$，表示贝壳的个数。
接下来一行一个长度为 n 的字符串，其中第 i 个字符表示第 i 个贝壳的颜色。'H' 代表红色，'L' 代表白色。
【输出格式】
一行一个数，表示满足条件的子序列的个数对 \(10^9 + 7\) 取模后的结果。
【数据范围】
对于 50% 的数据，满足 \(n ≤ 15\)。
对于 80% 的数据，满足 \(n ≤ 100\)。
对于 100% 的数据，满足 \(n ≤ 10^6\)。
【样例输入一】

3
HLH

【样例输出一】

6

【样例输入二】

3
HLL

【样例输出二】

5

【样例输入三】

10
LLLLHLLHHH

【样例输出三】

72

定义\(dp_{i,j}\)为前i个数最后一个为红/白时有多少种方案数。那么如果这一位是红,那么白的方案数不变，红的为上一位白的(用上这一位)加上上一位为红的(不用这一位).初始化\(dp_{0,0}=dp_{0,1}=1\),因为只有一种可能性。然后再最后要把答案减去2，因为要求非空。