{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003e商人 Petya 最近买了一栋新房子。这栋房子有一层,有 \u003cnobr\u003e\u003ci\u003en\u003c/i\u003e × \u003ci\u003em\u003c/i\u003e\u003c/nobr\u003e 个正方形房间,按矩形排列。其中一些房间是食品储藏室,其他的是卧室。现在他想要连接所有卧室,使得任意一对卧室之间都只有一种路径。他只能在相邻的卧室之间(即有共同墙壁的卧室)建造门。现在他想要计算他可以这样做的不同方式的数量。\u003c/div\u003e\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003e第一行包含两个整数 \u003ci\u003en\u003c/i\u003e 和 \u003ci\u003em\u003c/i\u003e \u003cnobr\u003e(1 ≤ \u003ci\u003en\u003c/i\u003e, \u003ci\u003em\u003c/i\u003e ≤ 9)\u003c/nobr\u003e\u0026nbsp;— 矩形排列中的行数和列数。接下来的 \u003ci\u003en\u003c/i\u003e 行包含恰好 \u003ci\u003em\u003c/i\u003e 个字符,代表房子的地图,其中 \".\" 表示卧室,\"*\" 表示食品储藏室。保证房子中至少有一个卧室。\u003c/div\u003e\u003c/div\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003e输出连接卧室的方式数量,取模 10\u003csup\u003e9\u003c/sup\u003e。\u003c/div\u003e\u003c/div\u003e"}},{"title":"示例 1","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 2\r\n..\r\n..\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"示例 2","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 2\r\n*.\r\n.*\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}