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:
is not a madotsuki pattern.
Multiply test cases, for each test case:
n m ( n ≤ 1000, m ≤ 10)
[ n*m '0', '1' or '?' ]
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.