Bob is at the local park! The park can be seen as an X
and all other squares are denoted with an O
.
Bob knows that the value of a picnic depends on the region covered. More precisely, if the picnic's region is an
Bob isn't sure if this park is the best for a picnic, so he wants to know the sum of the values of all possible picnic locations in this park. As the answer may be very large, he will be satisfied with knowing the answer modulo
Constraints
Note that this problem has no partial points.
Input Specification
The first line will have two space-separated integers,
The next X
's or O
's. This grid represents the park. Picnics may only be set up over rectangles which contain only O
's.
Output Specification
Output the sum of the values of all possible picnic locations modulo
Sample Input 1
2 3
OXO
OXX
Sample Output 1
16
Explanation for Sample 1
There are four possible picnic locations:
BXO OXO BXO OXB
OXX BXX BXX OXX
Their values are
Sample Input 2
3 3
XOX
OOO
XOX
Sample Output 2
218
Explanation for Sample 2
There are
XBX XOX XOX XOX XOX XBX XOX XOX XOX XBX XOX
OOO BOO OBO OOB OOO OBO BBO OBB OBO OBO BBB
XOX XOX XOX XOX XBX XOX XOX XOX XBX XBX XOX
Their values are
Comments
Since the original data were weak, an additional test case was added, and all submissions were rejudged.