金字塔

给定长度为 n 的字符串 s。从 s 中提取子序列，组成 pyramid 字符串的方法有多少种？答案需对 109+7取模后输出。

时间限制：1000ms内存限制：256MB

输入格式

第一行：一个整数 n;

第二行：一个字符串 s。

输出格式

输出组成 pyramid 的方法数（取模 109+7）。

输入样例#1

5
pxxxx

输出样例#1

0

输入样例#2

10
pyyradmiid

输出样例#2

4

数据范围：

1≤N≤105，s 仅包含小写英文字母。