{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eNothing is more beautiful than square! So, given a grid of cells, each cell being black or white, it is reasonable to evaluate this grid’s beautifulness by the side length of its maximum continuous subsquare which fully consists of white cells.\u003cbr\u003e\u003cbr\u003eNow you’re 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.\u003cbr\u003e\u003cbr\u003e\u003ccenter\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/2c991820ab85c251ad3fce73d5762ce3?v\u003d1715837495\"\u003e\u003c/center\u003e\u003cbr\u003eFor example, N \u003d 3 and there are 4 broken cells as shouwn in Fig. J(a). There are 2 painting schemes for i\u003d2 as shown in Fig. J(b) and J(c).\u003cbr\u003e\u003cbr\u003eYou just need to output the answer modulo 10\u003csup\u003e9\u003c/sup\u003e + 7.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains an integer T (T ≤ 10) denoting the number of the test cases.\u003cbr\u003e\u003cbr\u003eFor 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."}},{"title":"Output","value":{"format":"HTML","content":"For each test case, for each integer i between 0 and N inclusive, output the answer in a single line."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n3\r\noo*\r\nooo\r\n***\r\n8\r\noooooooo\r\noooooooo\r\noooooooo\r\noooooooo\r\noooooooo\r\noooooooo\r\noooooooo\r\noooooooo\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n29\r\n2\r\n0\r\n1\r\n401415247\r\n525424814\r\n78647876\r\n661184312\r\n550223786\r\n365317939\r\n130046\r\n1\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}