题目内容

塔子哥是一名小学生，他非常喜欢玩文字游戏。有一天，他在家里发现了一些单词，这些单词的长度不同，但是他想要将它们按照单词长度进行排序。因为他非常聪明，所以他很快就想到了一个方法：对于同一个长度的单词，他可以任意安排它们的位置。于是，他开始了他的排序之旅。

现在塔子哥拿到了一些单词， 他准备将这些单词按照单词长度进行非降序排序。对于同一个长度的单词，塔子哥可以任意安排它们的位置。

塔子哥想知道，最终有多少种不同的排序方式？由于答案可能过大，请对 $10^9+7$ 取模。

我们定义，如果两个方案排序后的字符串不同，则视为两种方案。

输入描述

第一行输入一个正整数 $n$ ，代表单词的数量。

第二行输入一行字符串，仅包含小写字母和空格。两个单词之间保证恰好有一个空格。

$1 \le n \le 100000$

所有单词的长度之和不超过 $300000$ 。

输出描述

最终的方案数对 $10^9 + 7$ 取模的值。

样例

样例一：

输入

3
tazi ta zi

输出

2