Girls Invitational '18 S5 - Mapping the Hill

View as PDF
Submit solution
Points: 12
Time limit: 2.0s
Memory limit: 64M
Author:
CoffeeWorld
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

Comments


  • 1
    Ninjaclasher  commented on March 23, 2019, 5:08 p.m.

    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.


    • 1
      StirFry  commented on March 24, 2019, 12:42 a.m.

      Nice


  • 2
    loluwot  commented on Dec. 23, 2018, 11:58 a.m.

    lower bound and upper bound of what?