作为安全部门的领导，请您检查贵公司一个古老的匹配系统。

系统被输入两个字符串，一个待匹配字符串和一个模式字符串，并判断前者是否能匹配后者。前一个字符串是严格的二进制字符串，后一个字符串由四种字符类型组成， *表示匹配零个或多个任意二进制字符，^表示精确匹配一个二进制字符。

系统有两种匹配方式:最大匹配和最小匹配。

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

系统将从LL到00枚举ii，其中LL为待匹配字符串的剩余长度。每次枚举开始前，系统消耗1个单位的能量。然后，它暂时假定模式字符串中的当前与待匹配字符串中连续的ii字符匹配，并尝试递归地匹配两个字符串的剩余位置。只要有一次尝试成功，系统就会放弃剩余的枚举并停止整个系统。否则，它将尝试下一个枚举，直到尝试了所有尝试并最终返回到前一个枚举。 如果要匹配的字符串已经用尽，系统将停止并返回到前面的枚举。否则，比较模式字符串和待匹配字符串之间的当前字符将消耗11个单位的能量。如果结果相同，它将继续分析这两个字符串的剩余位置，否则返回到前面的*枚举。 如果要匹配的字符串已经用尽，系统将停止并返回到之前的\textbf{}*枚举。否则，它会消耗11个单位的能量，并在两根弦上移动。 当模式字符串耗尽时，系统将同时检查待匹配的字符串。如果要匹配的字符串也用尽，它将返回并停止整个过程，否则，它将返回到前面的枚举。在尝试了所有尝试后，没有找到匹配的方法，系统最终将返回

最小匹配做类似的事情，除了枚举顺序(即，枚举ii从00到LL)。

这两种匹配方法似乎不是很有效，所以你想破解它们。请为每一种匹配方法都构造一个模式串和一个长度为nn的待匹配串，以使系统应答和能耗尽可能大。是的

输入格式 每个测试文件中只有一个测试用例。

第一行也是唯一一行包含一个整数n,(n <= 10^3 ) 输出格式 请在前3行中输出模式字符串、待匹配字符串和最大匹配方法的能耗。然后在接下来的3行中输出模式字符串、待匹配字符串和最小匹配方法的能量成本。

如果有多种构造方法，您可以输出其中的任何一种。

能量消耗可能非常大，所以你需要输出值模(10^9+7)(10 9 +7)。请注意，这只是为了您的方便，您需要在模数之前最大化能源成本