Latin Squares

문제

Chris is a fan of puzzles. Recently he learned about Sudoku puzzles, that are based on Latin squares. A $k\times kk\; \backslash times\; k$ table is called a Latin square if the number of distinct elements in the table is $kk$, and there are no two equal elements in the matrix that share the same row or the same column.

For example, [이미지 1], [이미지 2] and [이미지 3] are Latin squares, while [이미지 4], [이미지 5] and [이미지 6] are not.

Chris wants to make a new Latin square puzzle. However, he only has an old template, which is an $n\times mn\; \backslash times\; m$ table. Chris wants to cut a contiguous Latin square fragment from the template. In how many ways can he do this? Two ways to cut a square are considered different if there is a cell that is present in one square, but not present in the other.

입력

The first line contains two integers $nn$ and $mm$ --- dimensions of the template ($1\le n,m\le 20001\; \backslash le\; n,\; m\; \backslash le\; 2\backslash ,000$).

The next $nn$ lines contain strings $s_{i}s\_i$ that describe the template. Each string $s_{i}s\_i$ contains $2\cdot m2\; \backslash cdot\; m$ characters with ASCII codes between $3333$ and $126126$. The cell in row $ii$ and column $jj$ of the template contains a pair of characters $s_{i,2\cdot j-1}s\_\{i,\; 2\; \backslash cdot\; j\; -\; 1\}$ and $s_{i,2\cdot j}s\_\{i,\; 2\; \backslash cdot\; j\}$ ($1\le i\le n1\; \backslash le\; i\; \backslash le\; n$, $1\le j\le m1\; \backslash le\; j\; \backslash le\; m$). Two cells of the template contain equal elements if their ordered character pairs are equal. See the Notes section for further explanation.

출력

Print a single integer --- the number of ways to cut a Latin square from the template.

힌트

In the first sample there are $2020$ ways to cut a $1\times 11\; \backslash times\; 1$ Latin square, as well as $66$ other ways: