/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 250 点
問題文
N 行 N 列からなるグリッドがあります。グリッドの上から i 行目左から j 列目のマスは、S_{i,j} が # のとき黒く、. のとき白く塗られています。
このグリッドから縦 M 行横 M 列の領域を取り出して得られるマスの塗られ方は何種類ありますか？
制約
- 1\leq M \leq N \leq 10
- N,M は整数
- S_{i,j} は
.または#
入力
入力は以下の形式で標準入力から与えられる。
N M
S_{1,1}\ldots S_{1,N}
\vdots
S_{N,1}\ldots S_{N,N}
出力
答えを出力せよ。
入力例 1
3 2 ... ### #.#
出力例 1
3
与えられたグリッドの状態は下図左のとおりです。
ここから縦 2 行横 2 列の領域を取り出す方法は下図右のとおり 4 通りあり、マスの塗られ方は 3 種類あります。
入力例 2
10 3 ..#....... .###...... .#.#...... #####..... #...#..... ......#### ......#..# ......#... ......#..# ......####
出力例 2
36
Score : 250 points
Problem Statement
There is a grid with N rows and N columns. The cell at the i-th row from the top and j-th column from the left is painted black if S_{i,j} is #, and white if it is ..
How many distinct patterns of painted cells can be obtained by extracting a region of M rows and M columns from this grid?
Constraints
- 1\leq M \leq N \leq 10
- N and M are integers.
- S_{i,j} is
.or#.
Input
The input is given from Standard Input in the following format:
N M
S_{1,1}\ldots S_{1,N}
\vdots
S_{N,1}\ldots S_{N,N}
Output
Print the answer.
Sample Input 1
3 2 ... ### #.#
Sample Output 1
3
The state of the given grid is as shown in the left figure below.
There are four ways to extract a region of two rows and two columns from this grid as shown in the right figure below, and there are three distinct patterns of painted cells.
Sample Input 2
10 3 ..#....... .###...... .#.#...... #####..... #...#..... ......#### ......#..# ......#... ......#..# ......####
Sample Output 2
36