本题为问题《C.绿》的困难版本，两题的唯一区别在于构成字符串的字符集的大小。

在古老的魔法图书馆中，两位年轻的魔法学徒小绿和小紫发现了一本记载着神秘二进制魔法的古籍。书中描述了一种通过复制特定咒语来增强魔法威力的方法。她们决定分别研究这个魔法的不同版本：
小绿获得了一段魔法咒语 ，这段咒语仅由字符 和 组成。她将这段咒语复制 次并连接起来，形成新的强化咒语 。例如，若 且 ，则 。
魔法古籍中提到，稳定的魔法序列必须满足单调不减的特性，即序列中不会出现 在 之后的情况。小绿想知道，这个强化咒语 中可以找出多少个不同的非空子序列是稳定的魔法序列。由于答案可能很大，请将答案对 取模后输出。

【名词解释】
非空子序列：从原字符串中任意删除字符，且保持剩余字符相对顺序不变所得到的新字符串，至少包含原字符串中的一个字符。即便子序列字符内容相同，像从 不同位置选取得到的 子序列，因选取位置有别，在序列构造意义上也不相同。

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：
第一行输入一个整数 ，表示字符串  复制的次数。 
第二行输入一个长度为 ，仅由字符  和  组成的字符串 ，在这个版本中，我们对字符集没有额外的限制。 
除此之外，保证单个测试文件中所有输入字符串  的长度总和不超过 。

对于每组测试数据，输出一个整数，表示字符串  中单调不减的子序列的数量。由于答案可能非常大，请将结果对  取模后输出。

3
1
0011
2
011
3
0101

15
39
447