It's a new winter season at Yellow Mountain ski resort. This time, the resort has hired you to calculate the amount of routes a person can go down the hill in certain areas so that they can put the information in their brochure.
A map of the hill is given as a square grid of rows and columns. Places where one can ski are marked with O
's, while trees and other impassable terrain are marked with X
's.
Skiers start at the spaces given at the top of the hill and can ski to one of the three squares directly or diagonally below them. They can end their descent at any of the open places at the bottom of the hill.
Input Specification
The first line contains , the height and width of the hill.
Then lines follow with X
's or O
's on each line
The next line contains the number of queries, , in which lines of and will follow, where , with being the lower bound and being the upper bound, inclusive, of the positions at the bottom of the hill the skiers can end at.
Output Specification
Output the number of paths given the bounds, modulo .
Sample Input
3
OXO
XOX
OXO
2
1 2
2 3
Sample Output
2
2
Comments
The test data have been fixed, and the problem statement has been updated accordingly. In particular, you must now modulo the answer, and the query bounds are now one-indexed. Sorry for the inconvenience.
Nice
lower bound and upper bound of what?
The hill