Girls Invitational '18 S5 - Mapping the Hill

View as PDF

Points: 12
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

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 $$N\ (1 \le N \le 100)$$, the height and width of the hill.

Then $$N$$ lines follow with $$N$$ X's or O's on each line

The next line contains the number of queries, $$Q\ (1 \le Q \le 10^5)$$, in which $$Q$$ lines of $$N_1$$ and $$N_2$$ will follow, where $$1 \le N_1 \le N_2 \le N$$, with $$N_1$$ being the lower bound and $$N_2$$ 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 $$10^9+7$$.

Sample Input

3
OXO
XOX
OXO
2
1 2
2 3

Sample Output

2
2