Practice on Toph

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

Move It!

By ishtupeed · Limits 1s, 512 MB

Few of my friends are working on a game called “Move It!”. It's a tile-based game played on an n×nn\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)(i, j), he/she can only move to square (i+1,j)(i+1, j) or (i,j+1)(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.

Input

The first line of the input will contain a single integer t(1t10)t (1 \leq t \leq 10), the number of test cases.

For each test case, there will be one integer n(1n1000)n (1 \leq n \leq 1000), the side-length of the square grid. The following nn lines each will contain nn characters. The characters can either be:

  • . denoting an empty square.
  • r denoting a rock.
  • f denoting a fruit.

Output

If it's not possible to reach the goal, print 1-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 109+710^9+7.

Sample

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

Discussion

Statistics


66% Solution Ratio

kzvd4729Earliest, Jan '21

kzvd4729Fastest, 0.1s

mahade31Lightest, 9.0 MB

Tahmid690Shortest, 874B

Submit

Login to submit

Editorial

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

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.