题目描述

Flandre 的背后的水晶，会按照她的心情点亮。我们可以把水晶点亮与否读成一个二进制数，像是 101001001000111100010000001 这样的。

• Sakuya：这个数是 7 的倍数啊
• F：你是怎么知道的
• S：我用正则表达式啊

• F：那你现在多了一个问题了

• • -

你现在多了一个问题了！给定一个数 $k$，请回答一个正则表达式 $R$，使得对于任意 $S$，$R$ 匹配字符串 $S$ 当且仅当 $S$ 是一个 $k$ 的倍数的二进制数。

关于正则表达式：你的正则表达式只能使用以下字符：

01()|+*?

我们使用全串匹配测试，所以你不需要使用 ^ 和 $。

关于 $S$：我们对你的正则表达式测试的 $S$ 符合以下条件：

• $S$ 仅由 0 和 1 组成，且非空
• $S$ 不会有前导 0，也不会就是 0

举例来说，当 $k = 7$ 时，我们要求你给出的 $R$ 匹配以下字符串：

• 111（十进制下为 $7$）
• 101001001000111100010000001（$86276225 = 12325175 \times 7$）

我们要求你给出的 $R$ 不匹配以下字符串：

• 110（十进制下为 $6$）
• 1000111011000111101010110000（$149715632 = 21387947 \times 7 + 3$）

我们对你给出的 $R$ 是否匹配以下字符串不关心：

• test
• 000001111（前导 0）
• 0（是的，$S$ 不会是 0）
• 空字符串

输入格式

仅有一行，包含 $k$

输出格式

仅有一行，包含你的正则表达式 $R$

样例

input

2

output

(0|1)*0

二进制数是 2 的倍数，当且仅当其末位为 0

数据范围与提示

有 10 个测试点，第 $i$ 个测试点有 $k = i$

程序输出不得超过 $50000$ 个字符

来源：是 https://www.codewars.com/kata/regular-expression-check-if-divisible-by-0b111-7/ 的加强版