为了成功举办 2019 shake! 而忙碌奔波的 Junseo 突然很好奇 NCsoft 的 NC 是什么的缩写。虽然他尝试组合了自己知道的单词，比如 "Next Company"、"Next Cinema" 等，但他并不知道正确答案是什么。也许不仅仅是使用以 N 和 C 开头的单词，像 "nullpoiNter exCeption" 这样的名字也是可能的？

苦思冥想的 Junseo 首先将自己知道的、含有 N 或 C 的单词列成了一个清单。然后，他决定写下用清单中总共 $N$ 个单词可以组成的所有“NC 字符串”，并向 NCsoft 咨询。Junseo 可以制作的“NC 字符串”定义如下：

• 从 Junseo 知道的单词中选择任意数量的单词。
• 在一个字符串中，同一个单词最多只能选择一次。
• 将选出的单词以任意顺序排列，拼接成一个字符串。
• 如果在生成的字符串中，字符 N 和 C 都有出现，且存在至少一个 C 出现在某个 N 的后面，那么这就是一个“NC 字符串”。

例如，如果 Junseo 的单词清单是 {"NEVER", "ENDING", "CHANGE", "NCSOFT"}，那么从中选择任意单词并排列得到的 "NCSOFT"、"NEVER ENDING CHANGE" 等都是“NC 字符串”。但是 "CHANGE ENDING" 不是“NC 字符串”。

此外，由于“NC 字符串”在单词之间会插入空格，因此当单词清单为 {"NC", "NCNC", "NCNCNC"} 时，"NC NCNC"、"NCNC NC"、"NCNCNC" 都是不同的“NC 字符串”。

Junseo 很好奇自己能制作出多少个“NC 字符串”。让我们来计算一下 Junseo 可以制作的“NC 字符串”的总数。由于组合的数量可能非常大，请输出其模 $1,000,000,007$ 的余数。

输入格式

第一行包含一个整数 $N$（$1 \le N \le 100,000$），表示 Junseo 知道的单词数量。

接下来的 $N$ 行，每行给出一个互不相同的单词。所有单词的长度在 $1$ 到 $10$ 之间（包含边界），且仅由大写英文字母组成。每个单词都至少包含一个字符 N 或 C。

输出格式

输出一行，表示 Junseo 可以制作的“NC 字符串”的总数模 $1,000,000,007$ 的余数。

样例

输入样例 1

4
NEVER
ENDING
CHANGE
NCSOFT

输出样例 1

55

输入样例 2

3
NC
NCNC
NCNCNC

输出样例 2

15