Description

O 和 T 通过几乎成为废品的芯片中没有损坏的部分勉强读取出了一些二进制信息。

以下是其中一段读取到的二进制信息的示例，其中 . 表示不能准确读取的二进制位：

+--------+------------------------------------------------+
|.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|
+--------+------------------------------------------------+

在如上所示的信息格式中，左侧是一个表示当前时间戳的用二进制表示的无符号整数，右侧是记录具体事件内容的字符串。

二人读取到了一段记录了 $N$ 件事件的日志，日志中每个时间戳都是由 $M$ 个二进制位表示的整数。由于具体事件内容较难直接恢复，二人打算从还原事件发生的时间点下手。如果事件记录器本身没有出现异常，$N$ 件事件应该按发生的先后顺序记录，排在后面的事件的时间戳应该不小于排在前面的时间戳。

现在给定这 $N$ 个长度为 $M$ 的破损的二进制时间戳 $s_1, \dots, s_N$。O 和 T 想知道日志中第 $N$ 件事件发生的最早时间，以及在这件事件发生时间最早的前提下，所有可能的时间戳还原方案的总数。

避免故事就此终结，不让灯火就此熄灭。

Input Format

从标准输入读入数据。

输入的第一行包含两个正整数 $N$ 和 $M$，表示事件的数量和时间戳的长度。保证 $1 \leq N, M \leq 200$。

接下来 $N$ 行，每行包含一个仅由 0、1 或 . 组成的长度为 $M$ 的字符串 $s_i$，表示第 $i$ 件事件的时间戳，其中 . 表示读取失败的二进制位。

Output Format

输出到标准输出。

如果存在将所有 $s_i$ 中的 . 还原成 0 或 1，使得 $N$ 个时间戳按不降顺序排列的方案，则输出一个长度为 $M$ 且仅包含 0 和 1 的字符串和一个非负整数，分别表示所有还原方案中 $s_N$ 可能被还原成的最小的时间戳，以及满足要求的还原方案总数对 $1\,000\,000\,007$ 取模的结果，中间由一个空格隔开。

否则，如果不存在还原方案，则输出 -1。

3 4
..10
.1.0
...1

0101 1

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

0101 4

3 4
111.
011.
0...

-1

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

00010110 2

4 48
0..10011...........00011....1001................
...10100...10101........01110101...10010...01001
...10011...00001...11001.......1...............1
...................10011...10101...11010...10101

001100110000000100110011000101010001101000010101 270016253

Hint

【样例 1 解释】

可以证明，所有满足时间顺序要求的还原方案中，$s_3$ 最小可以被还原成 0101。当 $s_3$ 对应 0101 时，只有 $1$ 种还原方案，其对应时间戳分别为 0010、0100 和 0101。

【样例 2 解释】

此时 $s_1$ 可能对应 0010 或 0011，而 $s_2$ 可能对应 0100 或 0101，故总共有 $4$ 种满足要求的还原方案。