MDT1 - Madotsuki Pattern

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


subir imagenes

(image taken from github.com/madotsuki)

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. Since the answer can be very huge, you only need to output it after mod 1,000,000,007.

Example

Input:
2 4
2 4 ???? ???? 4 6 ?????? ?1010? ?0101? ??????
Output:
1 8
6 4

Added by:xiaodao
Date:2013-01-25
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem

hide comments
2017-01-26 21:00:24
How can I know when I should stop scanning the input, if the number of test cases is not given? Is there a maximum number of test cases?
2013-01-27 16:55:57 :D
Yes, Alex's description is correct. I also tested the problem and everything seems to be ok.

Last edit: 2013-02-07 08:16:25
2013-01-27 11:53:19 :D
Thanks for removing the picture. You can still attach some other artwork. I saw there's a lot of it on net. Just be sure it's nothing drastic or controversial.
2013-01-27 02:53:57 xiaodao
Thanks to Alex Anderson. Maybe the sample data can give you some explaintion. Sorry for my poor English /w\ ...
2013-01-27 02:53:57 Alex Anderson
I think it is pretty clear what it means. Each ? could be 0 or 1. Suppose there are K question marks. Then there are 2^K different possible ways you could set up the board.

Of those boards, some of them have a maximum number of madotsuki. That is what it is asking - how many of the 2^K different possible boards have the maximum number.
2013-01-27 02:53:57 Ehor Nechiporenko
To Author, could you please clarify problem statement. Maximum answer is understood, but what does mean "how many design can reach the answer in total"?
How do you calculate this value?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.