The Chamber of Secrets
By Leandro Zatesko, UFFS 
Brazil
By Leandro Zatesko, UFFS Brazil
The city of Chapecó, in the west of the brazilian state of Santa Catarina, is where are located the governance of the Federal University of Southern Border and one of the 6 campi of the university. In the next August 25, the 98th anniversary of the city shall be celebrated, and the city councilmen are already making the preparations for the party. The goal of this party, besides the anniversary celebration, is to raise funds to the construction of the new city Council's building, which is going to be a Chamber of Secrets, where the city councilmen will be able to vote more peacefully the increases of the bus fare without being so disturbed by the students.
The Chamber of Secrets is going to be a real maze, so eventual invaders will not exit so easily. But the architects are not sure about the plan and want to make some changes in the project. In order to make the work easier, they have projected the entire plan of the building over a grid of square units, so that each square unit would be either fully wall or free space, as in the figure below.
Willing to attack the problem in a more restricted manner, the architects have even picked up some regions of the plan so they could study each region isolated. Now, they want to know what is the number of possibilities they have to rearrange the square units of wall of each region only inside the region itself. For example, for the region highlighted in the figure above, there are 5 possibilities, which we illustrate in the figure below.
The first line of the input tells the dimensions N and M (1 ≤ N, M ≤ 50) of the plan in square units, which represent respectively the number of lines and the number of columns of the grid, and the N following lines describe the grid, so that free square units are represented by the character ‘.’ and wall square units by the character ‘#’. Each one of the remaining lines of the input consists of four integers xA, yA, xB and yB (1 ≤ xA < xB ≤ N, 1 ≤ yA < yB ≤ M), which define a region by the up-leftmost point (xA, yA) and by the down-rightmost point (xB, yB) of the regions. The input ends in end of file.
For each region described in the input, print a line containing singly the number of possibilities the architects have to rearrange the square unities of wall of the region only inside the region itself. As the number of possibilities can be very large, print only the remainder that is left when this number is divided by 109 + 7.
| Input Samples | Output Samples |
|
4 6 |
5 |