在一次针对古代遗迹的考察中，awdec 发现了一台古老的“星纹拼接机”。这台机器能够通过组合不同的字符碎片，合成出具有特殊能量的星纹长卷。
与此同时，同行的 Exusiai1 破译了一份被称为“星纹密钥”的古老卷轴。当拼接机合成出的星纹长卷中蕴含了“星纹密钥”的片段时，两者之间就会产生“共鸣”。
为了最大化共鸣产生的能量，awdec 和 Exusiai1 决定联手进行一次完美的拼接操作。

星纹拼接机的合成工作共分为 轮。初始时，存在一个空的星纹长卷 （即空串）。
在第 轮工作中，机器会提供两个备选的字符碎片 和 。awdec 必须且只能从中选择一个，将其直接拼接在当前长卷 的末尾。经过 轮选择后，将得到最终的星纹长卷 。
Exusiai1 提供的“星纹密钥”是一个字符串 。他们定义最终长卷 的共鸣强度为： 的每一个前缀在 中作为子串出现的次数之和。
awdec 想知道：
通过合理规划每一轮的选择，最终星纹长卷 的共鸣强度最大能达到多少？
在保证共鸣强度达到最大的前提下，共有多少种不同的选择方案？（注意：即使在某一步中 和 是两个完全相同的字符碎片（即 ），选择 和选择 依然被视为两种不同的方案。）
最终的方案数可能很大，请对 取模后输出。所有给定的字符串均只包含小写英文字母。

【名词解释】
字符串的前缀：从字符串的第一个字符开始，向后连续取若干个字符得到的字符串。更具体地，字符串 前 个字符构成的字符串被称为 的第 个前缀，也记为 。

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行包含一个整数 ，表示拼接的轮数。
第二行包含一个字符串 ，表示 Exusiai1 提供的星纹密钥。
接下来  行，第  行包含两个字符串  和 ，表示第  轮提供的两个备选字符碎片，中间以一个空格隔开。

除此之外，保证单个测试文件的  之和、 之和、 之和均不超过 。

对于每一组测试数据，在一行上输出两个整数，分别表示最大共鸣强度以及达到该最大值的方案数对  取模后的结果，两个整数之间以一个空格隔开。

3
2
abc
a x
bc a
1
a
a a
3
aba
a ab
ba a
a ba

3 1
1 2
7 2

对于第一组测试数据：
，它的前缀共有三个：。
唯一能达到最大共鸣强度的方案是：第一轮选择 ，第二轮选择 。拼接得到的最终长卷 。
在  中，前缀  出现了  次，前缀  出现了  次，前缀  出现了  次。总共鸣强度为 ，方案数为 。

对于第二组测试数据：
，前缀只有 。
第一轮提供的碎片 。选择  得到 ，共鸣强度为 ，选择  得到 ，共鸣强度也为 。
由于选择  和选择  视为不同方案，因此最大共鸣强度为 ，方案数为 。

对于第三组测试数据：
，它的前缀有：。
能达到最大共鸣强度的方案有两种：
方案一：选择 ，，，拼接得到 。
方案二：选择 ，，，拼接得到 。
在串  中：
 前缀  出现在位置 ，共  次。
 前缀  出现在位置 ，共  次。
 前缀  出现在位置 ，共  次。
总共鸣强度为 。共有  种方案可以得到该串。

在大部分情况下，PyPy 的运行速度优于 Python。本题我们建议您选择对应版本的 PyPy 进行提交、而不是 Python。