#include <bits/stdc++.h>
using namespace std;
void ga(int N, int *A) {
  for (int i(0); i < N; i++) scanf("%d", A + i);
}
char s[1024][1024];
void RL(int &a, int &b, int &c, int &d) {
  int t(a);
  a = b, b = c, c = d, d = t;
}
void rot(int r[][1024], int N) {
  for (int i(0); i < N >> 1; i++)
    for (int j(0); j < (N + 1) >> 1; j++)
      RL(r[i][j], r[N - 1 - j][i], r[N - 1 - i][N - 1 - j], r[j][N - 1 - i]);
}
int N, M, g[1024][1024], H[1024][1024], D[1024][1024], l;
long long S;
long long go() {
  long long S = 0;
  for (int j(0); j < N; j++)
    for (int i = N - 1; ~i; --i) H[j][i] = g[j][i] + H[j][i + 1];
  for (int j(0); j < N; j++)
    for (int i = N - 1; ~i; --i) D[i][j] = g[i][j] + D[i + 1][j];
  for (int i(0); i < N; i++)
    for (int j(0); j < N; j++)
      if (g[i][j]) S += (H[i][j] - 1) * (D[i][j] - 1);
  return S;
}
int main(void) {
  scanf("%d%d", &N, &M);
  for (int i(0); i < N; i++) scanf("%s", s[i]);
  N = M = max(N, M);
  for (int i(0); i < N; i++)
    for (int j(0); j < N; j++) g[i][j] = s[i][j] == 42;
  for (int i(0); i < 4; i++) S += go(), rot(g, N);
  printf("%lld\n", S);
  return 0;
}

### Prompt

Your challenge is to write a CPP solution to the following problem:

You are given a n × m field consisting only of periods ('.') and asterisks ('*'). Your task is to count all right triangles with two sides parallel to the square sides, whose vertices are in the centers of '*'-cells. A right triangle is a triangle in which one angle is a right angle (that is, a 90 degree angle).

Input

The first line contains two positive integer numbers n and m (1 ≤ n, m ≤ 1000). The following n lines consist of m characters each, describing the field. Only '.' and '*' are allowed.

Output

Output a single number — total number of square triangles in the field. Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preffered to use cout (also you may use %I64d).

Examples

Input

2 2
**
*.


Output

1


Input

3 4
*..*
.**.
*.**


Output

9

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
void ga(int N, int *A) {
  for (int i(0); i < N; i++) scanf("%d", A + i);
}
char s[1024][1024];
void RL(int &a, int &b, int &c, int &d) {
  int t(a);
  a = b, b = c, c = d, d = t;
}
void rot(int r[][1024], int N) {
  for (int i(0); i < N >> 1; i++)
    for (int j(0); j < (N + 1) >> 1; j++)
      RL(r[i][j], r[N - 1 - j][i], r[N - 1 - i][N - 1 - j], r[j][N - 1 - i]);
}
int N, M, g[1024][1024], H[1024][1024], D[1024][1024], l;
long long S;
long long go() {
  long long S = 0;
  for (int j(0); j < N; j++)
    for (int i = N - 1; ~i; --i) H[j][i] = g[j][i] + H[j][i + 1];
  for (int j(0); j < N; j++)
    for (int i = N - 1; ~i; --i) D[i][j] = g[i][j] + D[i + 1][j];
  for (int i(0); i < N; i++)
    for (int j(0); j < N; j++)
      if (g[i][j]) S += (H[i][j] - 1) * (D[i][j] - 1);
  return S;
}
int main(void) {
  scanf("%d%d", &N, &M);
  for (int i(0); i < N; i++) scanf("%s", s[i]);
  N = M = max(N, M);
  for (int i(0); i < N; i++)
    for (int j(0); j < N; j++) g[i][j] = s[i][j] == 42;
  for (int i(0); i < 4; i++) S += go(), rot(g, N);
  printf("%lld\n", S);
  return 0;
}

```