/ 
Time Limit: 8 sec / Memory Limit: 256 MB
問題文
12 月に入り、2014 年もそろそろ終わりを迎えようとしています。そこで、気分を一新するために壁紙の模様替えをして 2015 年を迎えることにしました。
手元に縦 R 行横 C 列の生地があったので、その生地を必要ならば一部を切り出して壁紙のデザインにすることにしました。
生地からデザインを切り出すとき、必ずマス目に沿って切らなければならず、かつデザインは長方形の形状をしていなければなりません。
生地を構成する各マスはそれぞれただ 1 つの色で塗られています。
実は毎年面白いデザインを追求しているので、今年も面白いデザインとして「点対称なデザイン」であるような型紙を作ることにしました。
デザインが「点対称なデザイン」であるとは、デザインの大きさを縦 H 行、横 W 列としたとき、
- H ≧ 2 および W ≧ 2 を満たす。
- すべての整数 i,j (1 ≦ i ≦ H, 1 ≦ j ≦ W) について、デザインの上から i 番目、左から j 番目のマスの色 c_{i,j} が、デザインの上から H-i+1 番目、左から W-j+1 番目のマスの色 c_{H-i+1,W-j+1} と等しい。
である場合のことを指すこととします。
生地の場所によって、色以外にも様々な興味深い点があるので、縦横の大きさおよび色の配置が全く同じでも、切り出す元の場所が異なれば別のデザインとなります。そして、生地に対して「点対称なデザイン」であるデザインを 1 つ切り出す方法が全部で何通りあるか知りたいと思っています。
入力
入力は以下の形式で標準入力から与えられる。
R C s_1 s_2 : s_R
- 1 行目には、生地の行数 R (1 ≦ R ≦ 250) および列数 C (1 ≦ C ≦ 250) が空白区切りで与えられる。
- 2 行目から R 行には、生地の配色に関する情報が与えられる。このうち i (1 ≦ i ≦ R) 行目には長さ C の文字列 s_i が与えられる。s_i は半角小文字英字のみで構成されており、左から j (1 ≦ j ≦ C) 文字目は、生地の上から i 番目、左から j 番目のマスの色を表す。
- 異なる 2 つのマスについて、上記の色を表す文字が同じなら同じ色で、異なるなら異なる色で塗られていることを表す。
部分点
この問題には部分点が設定されています。
- R ≦ 20 および C ≦ 20 を満たすデータセット 1 にすべて正解すると、15 点が得られます。
- R ≦ 100 および C ≦ 100 を満たすデータセット 2 にすべて正解すると、上記に加えてさらに 30 点が得られます。
- 追加制約のないデータセット 3 にすべて正解すると、上記に 2 つに加えてさらに 55 点が得られ、全体で 100 点が得られます。
出力
「点対称なデザイン」であるデザインの個数を 1 行に出力せよ。出力の末尾にも改行を入れること。
入力例1
2 10 codethanks documentsk
出力例1
2
生地の配色は下表のようになっています。
| c | o | d | e | t | h | a | n | k | s |
| d | o | c | u | m | e | n | t | s | k |
例えば、上から 1 番目、左から 1 番目のマスを左上端、上から 2 番目、左から 3 番目のマスを右下端とした縦 2 行横 3 列の領域を切り出すと、
| c | o | d |
| d | o | c |
となり、「点対称なデザイン」が切り出せます。他にも、1 つ切り出せる場所があるので、答えは 2 となります。
入力例2
6 4 aaaa abba abba aaaa ccbb cdbb
出力例2
5
ある「点対称なデザイン」が別の「点対称なデザイン」を含んでいてもそれぞれ数えます。
また、この例の場合、
| b | b |
| b | b |
が 2 箇所に出てきますが、2 つとも数えます。