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

(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