F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

Square

Time Limit: 24000/12000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 443    Accepted Submission(s): 298


Problem Description
Nothing is more beautiful than square! So, given a grid of cells, each cell being black or white, it is reasonable to evaluate this grids beautifulness by the side length of its maximum continuous subsquare which fully consists of white cells.

Now youre given an N N grid, and the cells are all black. You can paint some cells white. But other cells are broken in the sense that they cannot be paint white. For each integer i between 0 and N inclusive, you want to find the number of different painting schemes such that the beautifulness is exactly i. Two painting schemes are considered different if and only if some cells have different colors. Painting nothing is considered to be a scheme.


For example, N = 3 and there are 4 broken cells as shouwn in Fig. J(a). There are 2 painting schemes for i=2 as shown in Fig. J(b) and J(c).

You just need to output the answer modulo 109 + 7.
 

Input
The first line contains an integer T (T 10) denoting the number of the test cases.

For each test case, the first line contains an integer N (1 N 8), denoting the size of the grid is N N . Then N lines follow, each line containing an N-character string of o and *, where o stands for a paintable cell and * for a broken cell.
 

Output
For each test case, for each integer i between 0 and N inclusive, output the answer in a single line.
 

Sample Input
2 3 oo* ooo *** 8 oooooooo oooooooo oooooooo oooooooo oooooooo oooooooo oooooooo oooooooo
 

Sample Output
1 29 2 0 1 401415247 525424814 78647876 661184312 550223786 365317939 130046 1
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-06-17 02:07:48, Gzip enabled