O and T have managed to extract some binary information from the damaged chip, which was nearly scrap. The following is an example of a segment of the extracted binary information, where . represents a binary bit that could not be read accurately:

+--------+--------------------------------------------+
|.00.....|0..10011...........00011....1001...........|
|.00.111.|...10100...10101........01110101...10010...01001|
|.00.011.|...10011...00001...11001.......1...............1|
|.00.0...|...................10011...10101...11010...10101|
+--------+--------------------------------------------+

In the information format shown above, the left side is an unsigned integer represented in binary that indicates the current timestamp, and the right side is a string recording the specific content of the event.

The two have obtained a log recording $N$ events, where each timestamp in the log is an integer represented by $M$ binary bits. Since the specific event content is difficult to recover directly, they intend to start by restoring the time points at which the events occurred. If the event recorder itself did not malfunction, the $N$ events should have been recorded in the order they occurred, and the timestamp of a later event should not be less than the timestamp of an earlier event.

Now, given these $N$ damaged binary timestamps $s_1, \dots, s_N$ of length $M$, O and T want to know the earliest possible time the $N$-th event occurred, and under the premise that this event occurred at the earliest possible time, the total number of all possible timestamp restoration schemes.

Input

The input is read from standard input.

The first line contains two positive integers $N$ and $M$, representing the number of events and the length of the timestamps. It is guaranteed that $1 \le N, M \le 200$.

The next $N$ lines each contain a string $s_i$ of length $M$ consisting only of 0, 1, or ., representing the timestamp of the $i$-th event, where . represents a binary bit that failed to be read.

Output

Output to standard output.

If there exists a scheme to restore all . in $s_i$ to 0 or 1 such that the $N$ timestamps are in non-decreasing order, output a string of length $M$ containing only 0 and 1 and a non-negative integer, representing the minimum possible timestamp that $s_N$ can be restored to among all valid restoration schemes, and the total number of valid restoration schemes modulo $1,000,000,007$, separated by a space.

Otherwise, if no such restoration scheme exists, output -1.

Examples

Input 1

3 4
..10
.1.0
...1

Output 1

0101 1

Note

It can be proven that among all restoration schemes satisfying the chronological order requirements, the minimum $s_3$ can be restored to is 0101. When $s_3$ corresponds to 0101, there is only 1 restoration scheme, corresponding to the timestamps 0010, 0100, and 0101.

Input 2

3 4
..1.
.1..
...1

Output 2

0101 4

Note

In this case, $s_1$ can correspond to 0010 or 0011, and $s_2$ can correspond to 0100 or 0101, so there are a total of 4 valid restoration schemes.

Input 3

3 4
111.
011.
0...

Output 3

-1

Input 4

3 8
.00.111.
.00.011.
.00.0...

Output 4

00010110 2

Input 5

See 5.in and 5.ans in the problem directory.