This content is archived!For the 2018-2019 school year, we have switched to using the WLMOJ judge for all MCPT related content. This is an archive of our old website and will not be updated.
At the Yellow Mountain ski resort, one can find one of the best ski hills in the province. Not only is it the tallest, but one can take tons of unique routes down the hill!
A map of the hill is given as a square grid of N rows and columns. Places where one can ski are marked with
O’s, while trees and other impassible terrain are marked with
Skiers can start at any of the open spaces 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. Given a map of the hill, figure out in how many unique ways one can descend down the hill.
The first line of the input provides the number of test cases, T (1 \leq T \leq 100). T test cases follow. Each test case begins with an integer N (1 \leq N \leq 100). N lines follow, each containing N characters, either an
For each test case, your program should output one integer: the number of unique routes one can take down the hill, modulo 1\,000\,000\,007.
Explanation for Sample Output
In the first case, these are the four routes a skier can take: