Problem Description

On the $xy$ plane, there are several coins. The configuration of the coins is represented by a grid of $H$ rows and $W$ columns. The character $s_{ij}$ at the $i$-th row and $j$-th column of the grid indicates that there is a coin at coordinate $(i,j)$ if $s_{ij}$ is #, and no coin at coordinate $(i,j)$ if $s_{ij}$ is .. No other coins exist on the $xy$ plane.

Find the number of distinct triples of coins that satisfy the following condition:

• For any two coins among the three, the Manhattan distance between their coordinates is constant.

The Manhattan distance between coordinates $(x,y)$ and $(x',y')$ is represented by $|x-x'|+|y-y'|$. Additionally, triples that are merely permutations of each other are considered the same.

Input Format

The input is given from the standard input in the following format:

$ H $ $ W $ $ s_{11}...s_{1W} $ $ : $ $ s_{H1}...s_{HW} $

Output Format

Output the number of triples that satisfy the condition.

Sample Input and Output

Sample Input #1

5 4
#.##
.##.
#...
..##
...#

Sample Output #1

3

Sample Input #2

13 27
......#.........#.......#..
#############...#.....###..
..............#####...##...
...#######......#...#######
...#.....#.....###...#...#.
...#######....#.#.#.#.###.#
..............#.#.#...#.#..
#############.#.#.#...###..
#...........#...#...#######
#..#######..#...#...#.....#
#..#.....#..#...#...#.###.#
#..#######..#...#...#.#.#.#
#..........##...#...#.#####

Sample Output #2

870

Notes/Hints

Constraints

• $1 \leq H,W \leq 300$
• $ s_{ij} $ is either # or .

Sample Explanation 1

$((1,1),(1,3),(2,2)),((1,1),(2,2),(3,1)),((1,3),(3,1),(4,4))$ satisfy the condition.

见题面 Input 部分

见题面 Output 部分