匹配系统 - Problema

作为安全部门的负责人，你需要检查公司内部的一个古老匹配系统。

该系统接收两个字符串：一个待匹配字符串和一个模式字符串，并判断前者是否能与后者匹配。待匹配字符串是一个严格的二进制字符串（即仅包含 0 和 1），模式字符串由四种字符组成：0、1、*、^。其中 * 表示匹配零个或多个任意二进制字符，^ 表示匹配恰好一个二进制字符。

系统有两种匹配方法：最大匹配和最小匹配。

考虑两个字符串的起始位置。最大匹配方法会根据模式字符串的当前字符做出不同的决策：

*：系统将枚举 $i$ 从 $L$ 到 $0$，其中 $L$ 是待匹配字符串的剩余长度。在每次枚举开始前，系统消耗 $1$ 单位能量。然后，系统临时假设模式字符串中的当前 * 匹配待匹配字符串中连续的 $i$ 个字符，并尝试递归匹配两个字符串的剩余部分。只要有一次尝试成功，系统就会放弃剩余的枚举并停止整个系统。否则，它将尝试下一次枚举，直到所有尝试都已完成，最后返回到上一个 * 的枚举状态。
0, 1：如果待匹配字符串已耗尽，系统将停止并返回到上一个 * 的枚举状态。否则，它消耗 $1$ 单位能量来比较模式字符串和待匹配字符串的当前字符。如果结果相同，它将继续分析这两个字符串的剩余位置；否则，返回到上一个 * 的枚举状态。
^：如果待匹配字符串已耗尽，系统将停止并返回到上一个 * 的枚举状态。否则，它消耗 $1$ 单位能量并继续处理两个字符串的下一个位置。

当模式字符串耗尽时，系统会同时检查待匹配字符串。如果待匹配字符串也已耗尽，它将返回“Yes”并停止整个过程；否则，它将返回到上一个 * 的枚举状态。在尝试所有可能且未找到匹配方法后，系统最终将返回“No”。

最小匹配方法执行类似的操作，区别仅在于 * 的枚举顺序（即枚举 $i$ 从 $0$ 到 $L$）。

这两种匹配方法似乎效率不高，因此你想破解它们。请为每种匹配方法分别构造一个长度为 $n$ 的模式字符串和一个待匹配字符串，使得系统回答“Yes”且能量消耗尽可能大。

每个测试文件中仅包含一个测试用例。第一行包含一个整数 $n$ ($1 \le n \le 10^3$)，表示需要构造的字符串长度。

请在头 3 行输出最大匹配方法的模式字符串、待匹配字符串以及能量消耗。然后在接下来的 3 行中输出最小匹配方法的模式字符串、待匹配字符串以及能量消耗。

如果有多种构造方式，输出其中任意一种即可。

能量消耗可能非常大，因此你需要输出其对 $(10^9 + 7)$ 取模后的值。注意，这仅是为了方便起见，你需要在取模前使能量消耗最大化。

*0*
011
8
**1
101
7

QOJ.ac