Binary Subsequences

The scientific committee is in deep trouble: they came up with a nice task, but they are not sure they can build the test data for it. The problem statement reads like this:

"Given a string containing only 0s and 1s, compute the number of distinct non-empty subsequences that appear in it."

A subsequence of a string is a string obtained from the original string by erasing some of its characters (possibly none). Two subsequences are considered different if and only if they differ in at least one position or have different lengths. For example, the string "101" has 6 distinct non-empty subsequences: "0", "1", "10", "01", "101" and "11".

The committee could, of course, generate the tests randomly and compute the answer for each of them with the official source, but this idea does not satisfy the author. They want full control over the output. For each value K in a given file, they want to know how many binary strings have exactly K distinct non-empty subsequences and what the shortest such string is. If more than one string meets the requirements, any such string is accepted. Since the answer to the first question can be very large, they want to know it modulo 1,000,000,007.

The first line of the input contains a number T, the number of values K that follow. The next T lines contain the values of K for which you must answer the 2 queries described in the statement.

For each value K in the input file, print 2 lines:

On the first line, print the number of binary strings that have exactly K distinct non-empty subsequences, modulo 1,000,000,007, or -1 if you want to skip this query. If you print any number other than -1, we consider that you attempted to answer the question.

On the second line, print -1 if you want to skip the query. Otherwise, print L binary digits separated by spaces. These digits must form one of the binary strings of minimal length that have exactly K distinct non-empty subsequences.

• T ≤ 10
• K ≤ 1,000,000

For K = 2, exactly 2 strings have 2 distinct non-empty subsequences: "00" (with subsequences "0" and "00") and "11" (with subsequences "1" and "11"). Note that the string "11" also has minimum length, so the grader accepts it as a correct answer.

For K = 3, 4 strings satisfy the requirement: "10" (with subsequences "0", "1" and "10"), "01" (with subsequences "0", "1" and "01"), "000" (with subsequences "0", "00" and "000"), "111" (with subsequences "1", "11" and "111").

We skipped the first query for K = 8, and "1100" has exactly 8 distinct non-empty subsequences: "0", "00", "1", "11", "110", "1100", "10" and "100".