URI Online Judge | 1234

A Câmara Secreta

Por Leandro Zatesko, UFFS BR Brazil

Timelimit: 3

A cidade de Chapecó, no oeste do estado brasileiro de Santa Catarina, é onde ficam situados a Reitoria da Universidade Federal da Fronteira Sul e um dos 6 campi da universidade. No próximo dia 25 de agosto, comemorar-se-ão os 98 anos da cidade, e os vereadores já estão organizando os preparativos da festa. O objetivo desta festa, além da celebração do aniversário da cidade, é arrecadar fundos para a construção da nova Câmara de Vereadores, a qual será uma Câmara Secreta, onde os vereadores poderão votar mais tranquilamente os aumentos da tarifa de ônibus sem serem tão incomodados pelos estudantes.

A Câmara Secreta será um verdadeiro labirinto, isso para que eventuais invasores não consigam sair com tanta facilidade. Mas os arquitetos ainda não estão certos quanto à planta e querem fazer modificações no projeto. Para facilitar o trabalho, eles projetaram toda a planta sobre um grid de unidades quadradas, de modo que cada unidade quadrada fosse integralmente parede ou integralmente espaço livre, como na figura abaixo.

Visando atacar o problema de modo mais restrito, os arquitetos ainda elegeram algumas regiões da planta para estudarem cada região isoladamente. Agora, eles querem saber qual o número de possibilidades que têm para rearranjar as unidades quadradas de parede de cada região apenas dentro da própria região. Por exemplo, para a região destacada na figura acima, há 5 possibilidades, as quais ilustramos na figura abaixo.

Entrada

A primeira linha da entrada informa as dimensões N e M (1 ≤ N, M ≤ 50) da planta em unidades quadradas, as quais representam respectivamente o número de linhas e o número de colunas do grid, e as N linhas seguintes descrevem o grid, de modo que unidades quadradas livres são representadas pelo caractere ‘.’ e unidades quadradas de parede pelo caractere ‘#’. Cada uma das demais linhas da entrada é composta por quatro inteiros xA, yA, xB e yB (1 ≤ xA < xBN, 1 ≤ yA < yBM), os quais definem uma região através do ponto superior esquerdo (xA, yA) e do ponto inferior direito (xB, yB) da região. A entrada termina em fim de arquivo.

Saída

Para cada região descrita na entrada, imprima uma linha contendo unicamente o número de possibilidades que os arquitetos têm para rearranjar as unidades quadradas de parede da região apenas dentro da própria região. Como o número de possibilidades pode ser muito grande, imprima apenas o resto que o número deixa quando dividido por 109 + 7.

Exemplos de Entrada Exemplos de Saída

4 6
#...#.
..#.#.
##....
......
2 2 3 3
3 3 4 6
1 1 4 6

5
0
134595