题目描述

As the leader of the safety department, you are asked to check an ancient matching system in your company.

The system is fed with two strings, a to-be-matched string and a pattern string, and will determine whether the former can match the latter. The former string is a strict binary string(i.e., contains only $\textbf{0}$ and $\textbf{1}$), and the latter string consists of four types of characters $\textbf{0}$, $\textbf{1}$, $\textbf{*}$, ^, where $\textbf{*}$ means match zero or more arbitrary binary characters, and ^ means match exactly one binary character.

The system has two matching methods: maximum matching and minimum matching.

Consider the starting positions of the two strings. The maximum matching method will make different decisions based on the current character of the pattern string:

• $\textbf{*}$: The system will enumerate $i$ from $L$ to $0$, where $L$ is the remaining length of the to-be-matched string. Before each enumeration starts, the system consumes 1 unit of energy. Then it temporarily assumes that the current $\textbf{*}$ in the pattern string matches the consecutive $i$ characters in the to-be-matched string, and tries to match the remaining positions of two strings recursively. As long as one attempt is successful, the system will give up the remaining enumeration and stop the whole system. Otherwise, it will try the next enumeration until all attempts are tried and finally return to the previous $\textbf{*}$ enumeration.
• $\textbf{0,1}$: The system will stop and return to the previous $\textbf{*}$ enumeration if the to-be-matched string has been exhausted. Otherwise, it consumes $1$ unit of energy to compare the current characters between the pattern string and the to-be-matched string. It will continue analyzing the remaining positions of these two strings if the result is the same, otherwise, return back to the previous $\textbf{*}$ enumeration.
• ^: The system will stop and return to the previous $\textbf{*}$ enumeration if the to-be-matched string has been exhausted. Otherwise, it consumes $1$ unit of energy and moves on of two strings.

When the pattern string is exhausted, the system will check the to-be-matched string at the same time. It will return Yes and stop the whole process if the to-be-matched string is also exhausted, otherwise, it will return to the previous $\textbf{*}$ enumeration. After all attempts are tried and no matching method is found, the system will eventually return No.

Minimum matching does a similar thing except for the enumeration order of $\textbf{*}$ (i.e., enumerate $i$ from $0$ to $L$).

These two matching methods seem not very effective, so you want to hack them. Please construct both a pattern string and a to-be-matched string of length $n$ for each matching method, so that the system answers Yes and the energy consumption is as large as possible.

输入格式

There is only one test case in each test file.

The first and only line contains an integer $n$ ($1 \le n \le 10^3$) indicating the length of strings need to be constructed.

输出格式

Please output the pattern string, the to-be-matched string, and the energy cost for the maximum matching method in the first $3$ lines. Then output the pattern string, the to-be-matched string, and the energy cost for the minimum matching method in the next $3$ lines.

If there are multiple constructing ways, you can output any of them.

The energy cost may be very large, so you need to output the value modulo $(10^9+7)$. Note that this is only for your convenience and you need to maximize the energy cost before the modulus.

3

*0*
011
8
**1
101
7

提示

【题目描述】

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

该系统输入两个字符串，一个待匹配字符串和一个模式字符串，并确定前者是否能匹配后者。前者字符串是严格的二进制字符串（即仅包含 $\textbf{0}$ 和 $\textbf{1}$），而后者字符串由四种类型的字符组成 $\textbf{0}$、$\textbf{1}$、$\textbf{*}$ 和 ^，其中 $\textbf{*}$ 表示匹配零个或多个任意二进制字符，^ 表示匹配恰好一个二进制字符。

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

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

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

当模式字符串耗尽时，系统将同时检查待匹配字符串。如果待匹配字符串也已经耗尽，则系统将返回“是”并停止整个过程，否则，它将返回到先前的 $\textbf{*}$ 枚举。在尝试了所有尝试并找不到匹配方法后，系统最终将返回“否”。

最小匹配执行类似的操作，除了 $\textbf{*}$ 的枚举顺序（即从 $0$ 到 $L$ 枚举 $i$）。

这两种匹配方法似乎不太有效，所以你想黑掉它们。请为每种匹配方法构造一个长度为 $n$ 的模式字符串和待匹配字符串，使得系统返回“是”，能量消耗尽可能大。

【输入格式】

每个测试文件中只有一个测试用例。

第一行仅包含一个整数 $n$（$1 \le n \le 10^3$），表示需要构造的字符串的长度。

请输出最大匹配方法的模式字符串、待匹配字符串和能量消耗的前 $3$ 行。然后输出最小匹配方法的模式字符串、待匹配字符串和能量消耗的后 $3$ 行。

【输出格式】

如果有多种构造方式，你可以输出任何一种。

能量消耗可能非常大，所以你需要输出取模 $(10^9+7)$ 后的值。请注意，这仅供您方便，您需要在取模之前最大化能量消耗。

翻译来自于：ChatGPT。