小魚在做一道極其困難的題目，他已經做了好幾個月，但仍然做不出來。
「這題太難了啦，真希望有大神能助我一臂之力。」小魚自言自語地說道。
剛好路過的精靈小波聽到小魚的哀號聲，決定送給他一個神奇的道具。「試試看這個吧！」
精靈小波邊說邊遞給小魚一支筆。
「這支筆可不是一般的筆，只要用這支筆在地上畫出一個合法的魔法陣，就能召喚出大神來。」精靈小波解釋道。
「真的假的，謝謝你精靈小波。」小魚像是終於從枷鎖中解脫般不斷向精靈小波道謝。
一個合法的魔法陣是一個 $K \times K$ 的表格，其中 $K$ 可以是任意 $\geq 3$ 的正整數，同時每個格子上都有一個正整數。為了保證魔法陣能正常的啟動，還有幾個特殊的條件：
舉例來說，下圖兩個皆為可以正常啟動的魔法陣，特別注意到角落、邊界與內部的數字可以相同。
| 8 | 1 | 1 | 8 |
| 1 | 7 | 7 | 1 |
| 1 | 7 | 7 | 1 |
| 8 | 1 | 1 | 8 |
| 1 | 1 | 1 | 1 |
| 1 | 4 | 4 | 1 |
| 1 | 4 | 4 | 1 |
| 1 | 1 | 1 | 1 |
小魚他已經在地上畫了一個 $N \times M$ 表格，每個格子上都有一個正整數。但小魚患有選擇障礙症，他知道這個表格有很多子方陣是能正常啟動的合法魔法陣，但他不知道要選哪一個。請幫幫小魚計算有幾種子方陣是能正常啟動的合法魔法陣，兩種選法不同若且唯若兩個子方陣的大小不一樣，或是兩個矩陣的左上角的格子是從不同行或不同列來的。
輸入第一行有兩個正整數 $N, M$，代表表格有幾個橫列與幾個直排。
接下來 $N$ 行，第 $i$ 行有 $M$ 個正整數 $a_{i, 1}, a_{i, 2}, \ldots, a_{i, M}$，其中 $a_{i, j}$ 代表第 $i$ 個橫列的第 $j$ 格的數字是什麼。
請輸出一行，該行有一個整數代表有幾個子方陣是能正常啟動的合法魔法陣。
5 5 1 2 2 2 1 2 3 3 3 2 2 3 3 3 2 2 3 3 3 2 1 2 2 2 1
2
4 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
8
6 7 2 1 2 1 2 1 1 1 1 1 1 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 1 1 1 1 1 1 1 1 2 1 2 1 2 1
5
10 10 1 2 2 1 1 7 3 3 3 7 2 1 1 2 1 3 2 2 2 3 2 1 1 2 7 3 2 2 2 3 1 2 2 5 1 3 2 2 2 3 1 1 5 5 1 7 3 3 3 7 1 7 1 1 7 1 6 4 4 6 7 5 7 1 1 1 4 8 8 4 5 2 5 7 4 7 4 8 8 4 7 5 7 4 1 4 6 4 4 6 1 1 1 7 4 7 1 1 1 1
5
NPSC 2023 國中組決賽 pF 改
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~3 | 範例測資 | 0 |
| 2 | 4~8 | $a_{i, j} = 1$ | 5 |
| 3 | 9~18 | $N = 3$ | 3 |
| 4 | 0~3, 19~33 | $1 \leq N, M \leq 50$ | 10 |
| 5 | 0~3, 19~54 | $1 \leq N, M \leq 500$ | 26 |
| 6 | 4~8, 55~67 | 對於所有能正常啟動的合法魔法陣的子方陣，該子方陣內的數字皆相同 | 23 |
| 7 | 0~89 | 無額外限制 | 33 |