Madotsuki‘s Pattern

Time Limit: 8000/4000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

Madotsuki is the main character of the surreal adventure game Yumenikki.

The poor girl ended her life after discard all of her properties that have been found in the dream.

Every year there are some small celebrations among people.

The most symbolic sign of Madotsuki is the pattern on her clothes ...

You have been given a n*m design. Each element is one of the following character '1', '0', '?'.

You can freely choose each '?' to become '0' or '1', to maximizate the number madotsuki pattern in the design.

which the madotsuki pattern is somethings like this:

101

010

Remark

010

101

is not a madotsuki pattern.

Input

Multiply test cases, for each test case:

n m ( n ≤ 1000, m ≤ 10)

n*m '0', '1' or '?' ]

Output

For each test case, output the maximum answer, and how many design can reach the answer in total.

Mod 1e9+7 because the answer may be very huge.

Sample Input

2 4
????
????

4 6
??????
?1010?
?0101?
??????

Sample Output

1 8
6 4

Hint

求最多可以构造多少 “窗子花纹” 和,以及有多少可以得到这个最优解的方案数。

Source

xiaodao

Manager

Information
Solved Number1
Submit Number1
Problem Tags
dp
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel