---{"languages_supported":{"0":"NA"},"title":"M1","category":"NA","old_version":true,"problem_code":"M1","tags":{"0":"NA"},"layout":"problem"}---<h3> All submissions for this problem are available. </h3><p>It's 2012. The times of peace are over. The Trojan Kingdom has just declared war on Byteland! As part of a massive defense plan against the Trojans, the Bytelandian Ministry of Defense (BMoD) wants to lay mines on a field near the borderline of the country.</p><p>The field has the form of a MxN rectangular grid divided into MxN unit-square cells. It is only possible to plant mines on some cells, and the number of mines on a cell cannot exceed one.</p><p>The objective is obviously to lay as many mines as possible. However, the BMoD does not want any two adjacent cells to both have mines, because such a situation would be dangerous: one mine being triggered could lead to a chain of explosions! Two cells are adjacent if they share a common edge.</p><p>Johnny, the most renowned computer scientist in Byteland, needs to compute the maximum number of mines that could be planted on the field, and the number of different ways in which these mines could be planted.</p><p>Hurry up and help Johnny save his beloved country!</p><h3>Input</h3><p>The first line contains T (about 15), the number of test cases. Then T test cases follow. Each test case has the following form.</p><p>The first line contains two numbers M and N representing the size of the field (1 <= M, N <= 20).</p><p>Each line in the next M lines contains N characters. Each character is either '.' or '*' representing the status of a cell in the field. A character '.' represents an empty cell (i.e. it is possible to lay a mine on that cell), while a character '*' represents a blocked cell (i.e. there are obstacles on that cell which prevent mines from being laid on it).</p><p>Input for successive test case is separated by a blank line.</p><h3>Output</h3><p>For each test case, print two numbers on a line. The first number is the maximum number of mines that could be planted on the field. The second number is the number of ways to plant the maximum number of mines on the field, modulo 151109.</p><h3>Example</h3><pre><b>Input:</b>22 3....*.3 3....*....<b>Output:</b>3 14 2</pre><p></p>