시간 제한메모리 제한제출정답맞힌 사람정답 비율
6 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)3512952.941%

문제

$151$. 누군가에게는 아무 의미가 없을 수 있지만, 누군가에게는 엄청난 추억이 담긴 포켓몬 자체를 상징하는 수이다.

특히 한국어 정식발매가 없던 1세대부터 포켓몬을 번역까지 하며 플레이한 유틸에게는 더욱 애정이 넘치는 수이다.

여기까지 무슨 말인지 모르겠다면 구글에 151을 그대로 검색해 보자.

$151$은 또 다른 특징이 있다. 바로 $180^\circ$ 회전시켜도 같은 수라는 점이다. 유틸은 이에 착안해 새로운 문제를 만들었다.

꽤 많은 숫자들이 이러한 특징을 가지는데, $0$, $1$, $2$, $5$, $8$은 $180^\circ$ 회전했을 때 자기 자신이 되고, $6$과 $9$는 $180^\circ$ 회전했을 때 서로가 된다.

$0$ 이상 $9$ 이하의 정수 숫자로만 이루어진 $N$행 $M$열의 행렬이 주어진다. 여기서 그릴 수 있는 $\binom{N+1}{2}\times\binom{M+1}{2}$개의 직사각형들 중 직사각형을 통째로 $180^\circ$ 회전했을 때 원래와 같아지는 직사각형이 몇 개인지 궁금해졌다. 유틸을 도와 문제를 해결해 보자.

입력

첫 번째 줄에 행과 열의 수 $N,M(1\le N,M\le 500)$이 공백으로 구분되어 주어진다.

두 번째 줄부터 $N$줄에 걸쳐 각 행의 원소 $M$개가 공백 없이 주어진다.

출력

첫 번째 줄에 정답을 출력한다.

예제 입력 1

1 3
151

예제 출력 1

4

총 $\binom{2}{2}\times\binom{4}{2} =6$개의 직사각형 중, $1\times 1$ 모양의 직사각형 $3$개와 $1\times 3$ 모양의 직사각형 $1$개가 조건을 만족한다.

예제 입력 2

1 2
15

예제 출력 2

2

총 $\binom{2}{2}\times\binom{3}{2} =3$개의 직사각형 중, $1\times 1$ 모양의 직사각형 $2$개가 조건을 만족한다.

예제 입력 3

1 2
69

예제 출력 3

1

총 $\binom{2}{2}\times\binom{3}{2} =3$개의 직사각형 중, $1\times 2$ 모양의 직사각형 $1$개가 조건을 만족한다.

예제 입력 4

3 6
156951
777777
691196

예제 출력 4

12

예제 입력 5

9 9
151515151
515151515
151515151
515151515
151515151
515151515
151515151
515151515
151515151

예제 출력 5

1025

예제 입력 6

9 9
151515151
151515151
151515151
151515151
151515151
151515151
151515151
151515151
151515151

예제 출력 6

1125

예제 입력 7

9 9
111555111
111555111
111555111
555111555
555111555
555111555
111555111
111555111
111555111

예제 출력 7

477

예제 입력 8

9 9
696969696
969696969
696969696
969696969
696969696
969696969
696969696
969696969
696969696

예제 출력 8

1000

예제 입력 9

9 9
696969696
696969696
696969696
696969696
696969696
696969696
696969696
696969696
696969696

예제 출력 9

900

예제 입력 10

9 9
666999666
666999666
666999666
999666999
999666999
999666999
666999666
666999666
666999666

예제 출력 10

252
W3sicHJvYmxlbV9pZCI6IjM1MTQ4IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiJDE1MSQiLCJkZXNjcmlwdGlvbiI6IjxwPiQxNTEkLiBcdWIyMDRcdWFkNzBcdWFjMDBcdWM1ZDBcdWFjOGNcdWIyOTQgXHVjNTQ0XHViYjM0IFx1Yzc1OFx1YmJmOFx1YWMwMCBcdWM1YzZcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YzljMFx1YjljYywgXHViMjA0XHVhZDcwXHVhYzAwXHVjNWQwXHVhYzhjXHViMjk0IFx1YzVjNFx1Y2NhZFx1YjA5YyBcdWNkOTRcdWM1YjVcdWM3NzQgXHViMmY0XHVhZTM0IFx1ZDNlY1x1Y2YxM1x1YmFhYyBcdWM3OTBcdWNjYjRcdWI5N2MgXHVjMGMxXHVjOWQ1XHVkNTU4XHViMjk0IFx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkMmI5XHVkNzg4IFx1ZDU1Y1x1YWQ2ZFx1YzViNCBcdWM4MTVcdWMyZGRcdWJjMWNcdWI5ZTRcdWFjMDAgXHVjNWM2XHViMzU4IDFcdWMxMzhcdWIzMDBcdWJkODBcdWQxMzAgXHVkM2VjXHVjZjEzXHViYWFjXHVjNzQ0IFx1YmM4OFx1YzVlZFx1YWU0Y1x1YzljMCBcdWQ1NThcdWJhNzAgXHVkNTBjXHViODA4XHVjNzc0XHVkNTVjIFx1YzcyMFx1ZDJmOFx1YzVkMFx1YWM4Y1x1YjI5NCBcdWIzNTRcdWM2YjEgXHVjNTYwXHVjODE1XHVjNzc0IFx1YjExOFx1Y2U1OFx1YjI5NCBcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzVlY1x1YWUzMFx1YWU0Y1x1YzljMCBcdWJiMzRcdWMyYTggXHViOWQwXHVjNzc4XHVjOWMwIFx1YmFhOFx1Yjk3NFx1YWNhMFx1YjJlNFx1YmE3NCBcdWFkNmNcdWFlMDBcdWM1ZDAgPGNvZGU+MTUxPFwvY29kZT5cdWM3NDQgXHVhZGY4XHViMzAwXHViODVjIFx1YWM4MFx1YzBjOVx1ZDU3NCBcdWJjZjRcdWM3OTAuPFwvcD5cclxuXHJcbjxwPiQxNTEkXHVjNzQwIFx1YjYxMCBcdWIyZTRcdWI5NzggXHVkMmI5XHVjOWQ1XHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHViYzE0XHViODVjICQxODBeXFxjaXJjJCBcdWQ2OGNcdWM4MDRcdWMyZGNcdWNmMWNcdWIzYzQgXHVhYzE5XHVjNzQwIFx1YzIxOFx1Yjc3Y1x1YjI5NCBcdWM4MTBcdWM3NzRcdWIyZTQuIFx1YzcyMFx1ZDJmOFx1Yzc0MCBcdWM3NzRcdWM1ZDAgXHVjYzI5XHVjNTQ4XHVkNTc0IFx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWJiMzhcdWM4MWNcdWI5N2MgXHViOWNjXHViNGU0XHVjNWM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFmNjQgXHViOWNlXHVjNzQwIFx1YzIyYlx1Yzc5MFx1YjRlNFx1Yzc3NCBcdWM3NzRcdWI3ZWNcdWQ1NWMgXHVkMmI5XHVjOWQ1XHVjNzQ0IFx1YWMwMFx1YzljMFx1YjI5NFx1YjM3MCwgJDAkLCAkMSQsICQyJCwgJDUkLCAkOCRcdWM3NDAgJDE4MF5cXGNpcmMkIFx1ZDY4Y1x1YzgwNFx1ZDU4OFx1Yzc0NCBcdWI1NGMgXHVjNzkwXHVhZTMwIFx1Yzc5MFx1YzJlMFx1Yzc3NCBcdWI0MThcdWFjZTAsICQ2JFx1YWNmYyAkOSRcdWIyOTQgJDE4MF5cXGNpcmMkIFx1ZDY4Y1x1YzgwNFx1ZDU4OFx1Yzc0NCBcdWI1NGMgXHVjMTFjXHViODVjXHVhYzAwIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+JDAkIFx1Yzc3NFx1YzBjMSAkOSQgXHVjNzc0XHVkNTU4XHVjNzU4IFx1YzgxNVx1YzIxOCBcdWMyMmJcdWM3OTBcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0ICROJFx1ZDU4OSAkTSRcdWM1ZjRcdWM3NTggXHVkNTg5XHViODJjXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNWVjXHVhZTMwXHVjMTFjIFx1YWRmOFx1YjliNCBcdWMyMTggXHVjNzg4XHViMjk0ICRcXGJpbm9te04rMX17Mn1cXHRpbWVzXFxiaW5vbXtNKzF9ezJ9JFx1YWMxY1x1Yzc1OCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWI0ZTQgXHVjOTExIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc0NCBcdWQxYjVcdWM5ZjhcdWI4NWMgJDE4MF5cXGNpcmMkIFx1ZDY4Y1x1YzgwNFx1ZDU4OFx1Yzc0NCBcdWI1NGMgXHVjNmQwXHViNzk4XHVjNjQwIFx1YWMxOVx1YzU0NFx1YzljMFx1YjI5NCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NzQgXHViYTg3IFx1YWMxY1x1Yzc3OFx1YzljMCBcdWFkODFcdWFlMDhcdWQ1NzRcdWM4NGNcdWIyZTQuIFx1YzcyMFx1ZDJmOFx1Yzc0NCBcdWIzYzRcdWM2NDAgXHViYjM4XHVjODFjXHViOTdjIFx1ZDU3NFx1YWNiMFx1ZDU3NCBcdWJjZjRcdWM3OTAuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQ1ODlcdWFjZmMgXHVjNWY0XHVjNzU4IFx1YzIxOCAkTixNKDFcXGxlIE4sTVxcbGUgNTAwKSRcdWM3NzQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwICROJFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAgXHVhYzAxIFx1ZDU4OVx1Yzc1OCBcdWM2ZDBcdWMxOGMgJE0kXHVhYzFjXHVhYzAwIFx1YWNmNVx1YmMzMSBcdWM1YzZcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzgxNVx1YjJmNVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwic2FtcGxlX2V4cGxhaW5fMSI6IjxwPlx1Y2QxZCAkXFxiaW5vbXsyfXsyfVxcdGltZXNcXGJpbm9tezR9ezJ9ID02JFx1YWMxY1x1Yzc1OCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTUgXHVjOTExLCAkMVxcdGltZXMgMSQgXHViYWE4XHVjNTkxXHVjNzU4IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNSAkMyRcdWFjMWNcdWM2NDAgJDFcXHRpbWVzIDMkIFx1YmFhOFx1YzU5MVx1Yzc1OCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTUgJDEkXHVhYzFjXHVhYzAwIFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwic2FtcGxlX2V4cGxhaW5fMiI6IjxwPlx1Y2QxZCAkXFxiaW5vbXsyfXsyfVxcdGltZXNcXGJpbm9tezN9ezJ9ID0zJFx1YWMxY1x1Yzc1OCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTUgXHVjOTExLCAkMVxcdGltZXMgMSQgXHViYWE4XHVjNTkxXHVjNzU4IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNSAkMiRcdWFjMWNcdWFjMDAgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJzYW1wbGVfZXhwbGFpbl8zIjoiPHA+XHVjZDFkICRcXGJpbm9tezJ9ezJ9XFx0aW1lc1xcYmlub217M317Mn0gPTMkXHVhYzFjXHVjNzU4IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWM5MTEsICQxXFx0aW1lcyAyJCBcdWJhYThcdWM1OTFcdWM3NTggXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1ICQxJFx1YWMxY1x1YWMwMCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTVjXHViMmU0LjxcL3A+XHJcbiJ9LHsicHJvYmxlbV9pZCI6IjM1MTQ4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiJDE1MSQiLCJkZXNjcmlwdGlvbiI6IjxwPiQxNTEkLiBJdCBtaWdodCBub3QgbWVhbiBhbnl0aGluZywgYnV0IGZvciBzb21lLCBpdCBzeW1ib2xpemVzIGEgUG9rJmVhY3V0ZTttb24gd2hpY2ggYnJpbmdzIGJhY2sgaW5jcmVkaWJsZSBtZW1vcmllcy48XC9wPlxyXG5cclxuPHA+dXRpbEZvcmV2ZXImcnNxdW87cyBhZmZlY3Rpb24gZm9yIHRoaXMgbnVtYmVyIGlzIHBhcnRpY3VsYXJseSBzdHJvbmcgYmVjYXVzZSBoZSBoYXMgcGxheWVkIFBvayZlYWN1dGU7bW9uIHNpbmNlIEdlbmVyYXRpb24gSSBhbmQgZXZlbiB0cmFuc2xhdGVkIGl0IHdoZW4gdGhlcmUgd2FzIG5vIG9mZmljaWFsIEtvcmVhbiByZWxlYXNlLjxcL3A+XHJcblxyXG48cD5Ucnkgc2VhcmNoaW5nIDxjb2RlPjE1MTxcL2NvZGU+IG9uIEdvb2dsZSBpZiB5b3UgZG8gbm90IHVuZGVyc3RhbmQgd2hhdCB0aGlzIG1lYW5zIHNvIGZhci48XC9wPlxyXG5cclxuPHA+JDE1MSQgaGFzIGFub3RoZXIgY2hhcmFjdGVyaXN0aWMuIEl0IGlzIHRoZSBmYWN0IHRoYXQgaXQmcnNxdW87cyB0aGUgc2FtZSBudW1iZXIgd2hlbiByb3RhdGVkICQxODBeXFxjaXJjJC4gdXRpbEZvcmV2ZXIgY3JlYXRlZCBhIG5ldyBwcm9ibGVtIGJhc2VkIG9uIHRoaXMgaW5zcGlyYXRpb24uPFwvcD5cclxuXHJcbjxwPk1hbnkgZGlnaXRzIGhhdmUgdGhpcyBwcm9wZXJ0eSwgJDAkLCAkMSQsICQyJCwgJDUkLCAkOCQgcmVtYWluIHRoZSBzYW1lIHdoZW4gcm90YXRlZCBieSAkMTgwXlxcY2lyYyQsIHdoaWxlICQ2JCBhbmQgJDkkIGJlY29tZSBlYWNoIG90aGVyIHdoZW4gcm90YXRlZCBieSAkMTgwXlxcY2lyYyQuPFwvcD5cclxuXHJcbjxwPkFuICROJC1yb3cgJE0kLWNvbHVtbiBtYXRyaXggY29uc2lzdGluZyBvbmx5IG9mIGludGVnZXIgZGlnaXRzIGZyb20gJDAkIHRvICQ5JCBpcyBnaXZlbi4gSGUgYmVjYW1lIGN1cmlvdXMgYWJvdXQgaG93IG1hbnkgb2YgdGhlICRcXGJpbm9te04rMX17Mn1cXHRpbWVzXFxiaW5vbXtNKzF9ezJ9JCByZWN0YW5nbGVzIHRoYXQgY2FuIGJlIGRyYXduIGhlcmUgcmVtYWluIHVuY2hhbmdlZCB3aGVuIHRoZSBlbnRpcmUgcmVjdGFuZ2xlIGlzIHJvdGF0ZWQgYnkgJDE4MF5cXGNpcmMkLiBMZXQmcnNxdW87cyBoZWxwIHV0aWxGb3JldmVyIHNvbHZlIHRoZSBwcm9ibGVtLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIG51bWJlcnMgb2Ygcm93cyBhbmQgY29sdW1ucyAkTixNKDFcXGxlIE4sTVxcbGUgNTAwKSQgYXJlIGdpdmVuIGluIHRoZSBmaXJzdCBsaW5lIHNlcGFyYXRlZCBieSBhIHNwYWNlLjxcL3A+XHJcblxyXG48cD5Gcm9tIHRoZSBzZWNvbmQgbGluZSBhY3Jvc3MgJE4kIGxpbmVzLCAkTSQgZWxlbWVudHMgb2YgZWFjaCByb3cgYXJlIGdpdmVuIHdpdGhvdXQgc3BhY2VzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlByaW50IHRoZSBhbnN3ZXIgaW4gdGhlIGZpcnN0IGxpbmUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCIsInNhbXBsZV9leHBsYWluXzEiOiI8cD5BbW9uZyBhIHRvdGFsIG9mICRcXGJpbm9tezJ9ezJ9XFx0aW1lc1xcYmlub217NH17Mn0gPTYkIHJlY3RhbmdsZXMsICQzJCByZWN0YW5nbGVzIG9mIHNpemUgJDFcXHRpbWVzIDEkIGFuZCAkMSQgcmVjdGFuZ2xlIG9mIHNpemUgJDFcXHRpbWVzIDMkIHNhdGlzZnkgdGhlIGNvbmRpdGlvbi48XC9wPlxyXG4iLCJzYW1wbGVfZXhwbGFpbl8yIjoiPHA+QW1vbmcgYSB0b3RhbCBvZiAkXFxiaW5vbXsyfXsyfVxcdGltZXNcXGJpbm9tezN9ezJ9ID0zJCByZWN0YW5nbGVzLCAkMiQgcmVjdGFuZ2xlcyBvZiBzaXplICQxXFx0aW1lcyAxJCBzYXRpc2Z5IHRoZSBjb25kaXRpb24uPFwvcD5cclxuIiwic2FtcGxlX2V4cGxhaW5fMyI6IjxwPkFtb25nIGEgdG90YWwgb2YgJFxcYmlub217Mn17Mn1cXHRpbWVzXFxiaW5vbXszfXsyfSA9MyQgcmVjdGFuZ2xlcywgJDEkIHJlY3RhbmdsZSBvZiBzaXplICQxXFx0aW1lcyAyJCBzYXRpc2ZpZXMgdGhlIGNvbmRpdGlvbi48XC9wPlxyXG4ifV0=