科学委员会现在遇到了大麻烦：他们想出了一个不错的题目，但却不确定能否为此构建测试数据。题目描述如下：

“给定一个仅包含 0 和 1 的字符串，计算其中出现的不同非空子序列的数量。”

在此，字符串的子序列是指通过删除初始字符串中的某些字符（可能不删除）而得到的字符串。当且仅当两个子序列在至少一个位置上不同，或者它们的长度不同时，它们才被视为不同。例如，字符串 “101” 有 6 个不同的非空子序列：“0”、“1”、“10”、“01”、“101” 和 “11”。

现在，委员会当然可以随机生成测试数据，并用官方程序计算每个测试数据的答案，但这并不能满足出题人。他们希望完全掌控输出。他们想知道，对于给定文件中的每个值 $K$，有多少个二进制字符串恰好有 $K$ 个不同的非空子序列，以及满足该条件的最短字符串是什么。如果存在多个满足要求的字符串，委员会对其中任何一个都感到满意。由于第一个问题的答案可能非常大，他们只想知道该数量对 $1.000.000.007$ 取模后的结果。

输入格式

输入文件的第一行包含一个数字 $T$，表示后续 $K$ 值的数量。接下来的 $T$ 行包含你需要回答题目中描述的 2 个查询的 $K$ 值。

输出格式

对于输入文件中的每个值 $K$，你需要打印 2 行：

第一行，你应该打印恰好有 $K$ 个不同非空子序列的二进制字符串的数量（对 $1.000.000.007$ 取模），或者如果你想跳过此查询，则打印 -1。如果你打印的数字不是 -1，我们将认为你已尝试回答该问题。

第二行，如果你想跳过该查询，你应该打印 -1。否则，你应该打印由空格分隔的 $L$ 个二进制数字，这些数字应构成满足恰好有 $K$ 个不同非空子序列且长度最小的二进制字符串之一。

子任务

该问题共有 3 个子任务。你只能在第一个子任务中通过打印 -1 来跳过查询。

为了获得非零分数，你的每一个答案都必须是正确的，或者被跳过。设 $A$ 为第一个要求的正确答案数量，$B$ 为第二个要求的正确答案数量。你将获得： $$43 \times \frac{0.3 \times A + 0.7 \times B}{2000} \text{ 分}$$

样例

输入 1

3
2
3
8

输出 1

2
0 0
4
1 0
-1
1 1 0 0

说明

对于 $K = 2$，我们恰好有 2 个字符串具有 2 个不同的非空子序列：“00”（子序列为 “0” 和 “00”）以及 “11”（子序列为 “1” 和 “11”）。需要注意的是，字符串 “11” 也具有最小长度，会被评测系统接受为正确答案。

对于 $K = 3$，我们有 4 个字符串满足要求：“10”（子序列为 “0”、“1” 和 “10”）、“01”（子序列为 “0”、“1” 和 “01”）、“000”（子序列为 “0”、“00” 和 “000”）、“111”（子序列为 “1”、“11” 和 “111”）。

我们跳过了 $K = 8$ 的第一个查询，而 “1100” 恰好有 8 个不同的非空子序列：“0”、“00”、“1”、“11”、“110”、“1100”、“10” 和 “100”。

这只是一个澄清题目信息的示例。如你所见，$T$ 不等于 2000，因此这不可能是子任务 1 中的测试，这意味着通过跳过查询，我们将得到 0 分。