该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

【题目提示】

你可能会用到以下公式

• 若 $A 、 B、 M$ 都是正整数， 则 $( A + B ) \% M 与 ((A \% M) + (B \% M)) \% M 等价$ 。
• 若 $A 、 B、 M$ 都是正整数， 则 $( A * B ) \% M 与((A \% M) * (B \% M)) \% M 等价$ 。

【题目描述】

有一天，HakuroKawashiro（以下简称HK）从Tony那得到了一个问题。

• 给出一段长度为 $n$ 的只包含小写字母的字符串 $s$ ,从中选出6个字符按原先字符串顺序拼接成一个子串 $t$ ,问有多少种拼接方案可以拼接成子串qzsyoi？（答案对$1000000007$ 取模）

由于HK要完成琦哥给他布置的数学作业，然后和Tony一起玩雀魂。于是HK把这个问题交给你啦。

Input Format

第一行输入一个整数 $n$ 。

第二行一段长度为 $n$ 的只包含小写字母的字符串 $s$。

Output Format

输出一个数，表示拼接方案个数。（答案对$1000000007$ 取模）

Sample

【样例1输入】

8
qzzsyioi

【样例1输出】

2

【样例1解释】

注：标注黑体的字母为取出字母。

第一个方案：qzzsyioi

第二个方案：qzzsyioi

共2种方案。

【样例2输入】

60
qqqqqqqqqqzzzzzzzzzzssssssssssyyyyyyyyyyooooooooooiiiiiiiiii

【样例2输出】

1000000

Hint

对于 $15 \%$ 的数据，保证 $1 \leq n \leq 20$ 。

对于另外 $20 \%$ 的数据，保证字符串 $s$ 只有q 、z、s、y、o、i这6个字母并且按顺序输入，如qqqqzzzssyyyyooiiiii,qzzzssyyyyoooi等。

对于 $100 \%$ 的数据，保证 $1 \leq n \leq 10 ^ 5$ 。输入的字符只有小写字母。