我們都知道對於任何 $0 \le k \le n$，$\binom{n}{k} = \frac{n \cdot (n-1) \cdot \dots \cdot (n-k+2) \cdot (n-k+1)}{1 \cdot 2 \cdot \dots \cdot (k-1) \cdot k}$ 是一個整數。但如果我們能透過在分子與分母的因數之間提供一個匹配來證明這一點，豈不是很好嗎？

讓我們建立一個二分圖，其兩側各有 $k$ 個頂點。左側的第 $i$ 個頂點對應分子中的因數 $(n + 1 - i)$，右側的第 $j$ 個頂點對應分母中的因數 $j$。若且唯若 $j$ 整除 $(n + 1 - i)$ 時，存在一條邊 $i - j$。如果該二分圖中存在完美匹配，則稱數字 $k$ 對於 $n$ 是「可證明的」（provable）。

給定 $n$，請檢查對於每個滿足 $0 \le k \le n$ 的 $k$，該 $k$ 是否為可證明的。

輸入格式

輸入僅包含一個整數 $n$ ($0 \le n \le 10^{18}$)。

輸出格式

輸出一個長度為 $(n + 1)$ 的字串，由 '0' 和 '1' 組成，其中第 $(k + 1)$ 個字元為 '1' 若且唯若 $k$ 對於 $n$ 是可證明的。

你認為這會導致輸出超過限制（Output Limit Exceeded）嗎？嗯……好吧，讓我們壓縮這個字串。

令 $s_0 = \text{“0”}$ 且 $s_1 = \text{“1”}$。你可以定義 $s_2, s_3, \dots, s_t$。字串 $s_i$ 應為數個先前定義的字串之串接。形式上，$\forall i(2 \le i \le t) : s_i = s_{j_1} + s_{j_2} + \dots + s_{j_{k_i}}$，其中 $1 \le k_i$，且 $\forall r(1 \le r \le k_i) : j_r < i$。字串 $s_t$ 應為問題的答案。

在第一行輸出一個整數 $t$ ($2 \le t \le 500$)。 在接下來的 $t - 1$ 行中，輸出 $s_i$ 的描述。每個描述的形式應為 $k_i \ j_1 \ j_2 \ \dots \ j_{k_i}$，其中 $1 \le k_i$ 且 $0 \le j_r < i$。 所有描述的總長度不得超過 $10\,000$：$\sum_{i=2}^t k_i \le 10\,000$。

我們可以證明，對於所有有效的測試資料，都存在一種符合上述限制的構造答案字串的方法。如果有多種可能的方法，輸出其中任何一種即可。注意，你不需要最小化 $t$ 或所有描述的總長度。

範例

輸入格式 1

1

輸出格式 1

2
2 1 1

輸入格式 2

0

輸出格式 2

2
1 1

輸入格式 3

7

輸出格式 3

4
2 1 1
4 1 2 0 0
3 3 1 2

說明

在第三個範例中：$s_2 = s_1 + s_1 = \text{“1”} + \text{“1”} = \text{“11”}$，$s_3 = s_1 + s_2 + s_0 + s_0 = \text{“1”} + \text{“11”} + \text{“0”} + \text{“0”} = \text{“11100”}$，$s_4 = s_3 + s_1 + s_2 = \text{“11100”} + \text{“1”} + \text{“11”} = \text{“11100111”}$。