# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Few of my friends are working on a game called “Move It!”. It's a tile-based game played on an `$n\times n$`

square grid. Each square can either be empty or contain an object (a rock or a fruit).

The player starts from the top-left corner of the grid. If a player is in square `$(i, j)$`

, he/she can only move to square `$(i+1, j)$`

or `$(i, j+1)$`

in one move. However, if any square contains a rock, the player cannot move to that grid. If any square contains fruit, the player can collect the fruit by moving to that square. The goal is to reach the bottom-right corner of the grid while collecting as many fruits as possible.

My friends already built a demo version of the game and gave it to me to test it. To test the game thoroughly, I want to explore as many paths as possible that I can take to reach the goal by collecting the maximum possible amount of fruits.

It is guaranteed that the top-left corner and the bottom-right corner squares will be empty.

The first line of the input will contain a single integer `$t (1 \leq t \leq 10)$`

, the number of test cases.

For each test case, there will be one integer `$n (1 \leq n \leq 1000)$`

, the side-length of the square grid. The following `$n$`

lines each will contain `$n$`

characters. The characters can either be:

`.`

denoting an empty square.`r`

denoting a rock.`f`

denoting a fruit.

If it's not possible to reach the goal, print `$-1$`

.

Otherwise, print two space-separated integers denoting the maximum number of fruits I can collect to reach the goal and the possible number of paths that I can use to reach the goal while collecting that many fruits.

As the possible number of paths can be huge, print the count modulo `$10^9+7$`

.

Input | Output |
---|---|

2 3 .rr .ff ... 3 .rr rrf ff. | 2 1 -1 |

Login to submit

Let, The upper left square $\rightarrow (1, 1)$ Bottom right square $\rightarrow (n, n)$ The object...