Problem 3D 密码破译

时间限制：30 秒

空间限制：2048 MB

题目描述

对于一段由英文单词组成的语段 \(\{w_1,w_2,\cdots,w_n\}\)（\(w_i\) 是一个英文单词），以下流程可以称为"加密"。

• 对于每个单词，将首字母转为大写，其他字母转为小写。
• 将各个单词拼接，得到字符串 \(s\)。
• 随机打乱 \(s\) 的各个字符。

例如，\(\{time,for,dinner\}\) 可以通过以下方法"加密"

• 转换各个单词，并且拼接。即TimeForDinner
• 随机打乱各个字符，例如转换为 FirminnoDTere

示例

现在，给出一个词库 \(D\) 和待破译的字符串 \(s\)，已知 \(s\) 是由某语段 \(\{w_1,w_2,\cdots,w_n\}\) 按以上方法 "加密" 得到的，并且每个 \(w_i\) 是词库 \(D\) 中的单词。由于原始语段 \(\{w_1,w_2,\cdots,w_n\}\) 的可能性比较多，很难唯一确定它。所以你只需要求出满足要求的语段\(\{w_1,w_2,\cdots,w_n\}\) 的数量。

两个语段 A，B 不同，当且仅当：

• 存在单词 \(w\)，使得它在 A 中的出现次数与 B 中的出现次数不同。

换言之，单词的顺序对于语段来说是不重要的，\(\{time,for,dinner\}\) 和 \(\{for,dinner,time\}\) 视为同一个语段。

输入格式

第一行一个整数 \(n\)，表示词库的大小。

接下来 \(n\) 行每行一个字符串，表示词库中的一个单词。

最后一行一个字符串 \(s\)，是待破译的字符串。

输出格式

仅一个整数，表示可能的原始语段数量。

样例输入1

注意，在样例中我们省略了词库，在实际测试的时候则不会省略。

7500
...(省略7500行，每行一个单词)
cairAergaeatAGniMkmae

样例输出1

3

样例1解释

可能的语段如下所示：

again america gate maker 
again america great make 
america area gate making 

加密前，语段是 \(\{make,america,great,again\}\)。其他两种虽然看不出太多意义，但是也应当被计入答案中。

样例输入2

7500
...(省略7500行，每行一个单词)
nhEreBarlfgiInnnurfnntSinamtoTtveieuM

样例2解释

原始语段是 'Buffer', 'Sharing', 'In', 'Multi', 'Tenant', 'Environment'，但是也有数百种其他的可能。

我们不提供样例 2 的答案，并且将其作为第一组测试数据。

数据范围

共两组测试数据。

第一组测试数据 60 分，保证待破译的字符串为 nhEreBarlfgiInnnurfnntSinamtoTtveieuM。

第二组测试数据 40 分。

对于所有测试数据，\(n=7500\)，词库是固定的 7500 个常用词（你可以在 https://wwgm.lanzouy.com/ilLRY0umqhxe 获取这个词库）。待破译的字符串的单词数不超过 \(6\)，总长度不超过 \(40\)，可能的原始语段数量不超过 \(10^5\)。