DMOPC '17 Contest 3 P5 - Picnic Planning

View as PDF

Submit solution


Points: 15
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

Bob is at the local park! The park can be seen as an M by N grid. Bob can set up a picnic in a rectangle which has sides parallel to the grid's sides and does not partially cover any of the grid squares. Additionally, there are certain squares in the grid which Bob cannot set up a picnic over due to objects being in the way. These squares are denoted with 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 l by w rectangle, then Bob defines the value of a picnic to be lw(l^l+w^w). For example, if Bob sets up a picnic in a 2 by 3 rectangle, then its value would be 186.

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 10^9+7. Can you help him?

Constraints

1 \le M, N \le 2\,000

Note that this problem has no partial points.

Input Specification

The first line will have two space-separated integers, M and N.
The next M lines will each contain a single string composed of N 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 10^9+7.

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 2, 2, 10, and 2, so the answer is 16.

Sample Input 2

3 3
XOX
OOO
XOX

Sample Output 2

218

Explanation for Sample 2

There are 11 possible picnic locations:

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 2, 2, 2, 2, 2, 10, 10, 10, 10, 84, and 84, so the answer is 218.


Comments


  • 0
    maxcruickshanks  commented on July 5, 2023, 1:25 a.m.

    Since the original data were weak, an additional test case was added, and all submissions were rejudged.