F-牛牛写作文_牛客练习赛93

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

牛牛想要写一篇文章，他已经在脑中构造好了 $n$ 个句子。

但是因为句子实在是太多了！他并不想要自己筛选，于是他想要随机选一些句子构成一片文章。

所以牛牛每次会随机等概率地进行一下操作：

1. 停笔。即结束这篇作文。
2. 写下第 $1$ 个句子。
3. 写下第 $2$ 个句子。
4. $\cdots$
5. 写下第 $n$ 个句子。
也就是说，写下任意一个句子和停笔的概率都是 $\dfrac{1}{n+1}$ 。

写完作文后牛牛突然想起一个重要的句子必须写进作文里，但是作文已经写完了，牛牛只能祈祷在文章中找的到这个句子。

请你帮牛牛求出重要句子出现至少一次的概率，并对 $10^9+7$ 取模。

输入描述:

第一行一个整数 。

第  行到  行每行一个字符串。第  行的表示第  个句子。

第  行一个字符串 。表示重要的句子。

对于所有数据点，满足，所有字符串长度 ，且仅由小写字母组成。

输出描述:

一个整数表示重要句子至少只出现一次的概率对  取模的结果。

示例1

输入

复制

1
a
aa

输出

复制

250000002

说明

在第一步有停止写作，否则写下一个a

同样在第二步有的概率停止写作，否则再次写下一个a

所以写出aa的概率就是 =

示例2

输入

复制

3
ab
ba
a
aa

输出

复制

444444448

说明

样例答案为 。