Trie 分片

一个字符串集合 S 可以高效地存储在 *trie* 中。trie 是一棵有根树，对于 S 中每个字符串的每个前缀都有一个节点，没有重复。

例如，如果 S 是 "AAA", "AAB", "AB", "B"，对应的 trie 将包含 7 个节点，分别对应前缀 "", "A", "AA", AAA", "AAB", "AB", 和 "B"。

我有一个服务器，用一棵大 trie 存储 S。不幸的是，S 变得非常大，我无法将所有内容放入一个服务器的内存中。为了解决这个问题，我想改为将 S 存储在 N 个独立的服务器上。具体来说，S 将被划分为不相交的非空子集 T$_{1}$, T$_{2}$, ..., T$_{N}$，并且在每个服务器 i 上，我将构建一棵仅包含 T$_{i}$ 中字符串的 trie。这种方法的缺点是所有 N 棵 trie 的节点总数可能会增加。更糟糕的是，我无法控制字符串集合如何划分！

例如，假设 "AAA", "AAB", "AB", "B" 被分成两个服务器，一个包含 "AAA" 和 "B"，另一个包含 "AAB", "AB"。那么第一个服务器上的 trie 需要 5 个节点 ("", "A", "AA", "AAA", "B")，第二个服务器上的 trie 也需要 5 个节点 ("", "A", "AA", "AAB", "AB")。在这种情况下，两个服务器总共需要 10 个节点，而如果我可以将所有内容放在一个服务器上，则只需要 7 个节点。

给定字符串到 N 个服务器的分配，我想计算所有服务器上节点总数的最坏情况，以及这种情况发生的可能性有多大。然后我可以决定我的计划是好的还是风险太大。

给定 S 和 N，我可能得到的最大的节点总数是多少？此外，有多少种选择 T$_{1}$, T$_{2}$, ..., T$_{N}$ 的方式使得节点总数最大？注意 N 个服务器是不同的——如果一个字符串在一种安排中出现在 T$_{i}$，在另一种安排中出现在 T$_{j}$ (i != j)，那么这两种安排被认为是不同的。输出可能的安排数除以 1,000,000,007 后的余数。