24177번 - 引っ越し 다국어

あなたは昨今の事情を踏まえて広い部屋に引っ越すことにした．新しい部屋の間取りは正方形のマス目を縦 H マス，横 W マスに並べたグリッドで表すことができる．それぞれのマスは壁や柱のような侵入できないマス（以下，壁マスと呼ぶ）か，それ以外のマス（以下，床マスと呼ぶ）である．

あなたが新しい部屋の間取りを SNS で共有したところ，引っ越し祝いと称して友人からマス目のちょうど 3 マスを覆う大きさの L 字型のタイルカーペットがたくさん送られてきた．なんでもその友人が言うところによると，あなたの新しい部屋の間取りならば，L 字型のタイルカーペットをマス目に沿って適切に配置することで，タイルカーペットが重なることなく全ての床マスをタイルカーペットで覆うことができるらしい．

あなたは実際にタイルカーペットを敷く前に，全ての床マスを覆うことができるような配置が何通りあるのか調べることにした．組合せを数える際には個々のタイルカーペットは区別せず，タイルカーペットには裏表の区別がないこととする．

入力は複数のデータセットからなる．各データセットは次の形式で表される．

H W
a1,1 ... a1,W
...
aH,1 ... aH,W

1 行目には部屋の間取りを表すグリッドの大きさを表す 2 つの整数 H, W (2 ≤ H, W ≤ 8) が与えられる．続く H 行はそれぞれ W 文字からなり，各文字は壁マスを表す '#' と床マスを表す '.' のいずれかである．

部屋の間取りを表すグリッドは以下の制約を満たす．

• 床マスが 3 つ以上ある．
• タイルカーペットが重なることなく全ての床マスをタイルカーペットで覆うことができる配置が 1 通り以上ある．

入力の終わりは二つのゼロからなる行で表される．データセットの個数は 50 を超えない．

各データセットについて，すべての床マスが L 字型のタイルカーペットで覆われるような配置の組合せの数を 1 行で出力せよ．