C - March

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 300

問題文

N 人の人がいて、i 番目の人の名前は S_i です。

この中から、以下の条件を満たすように 3 人を選びたいです。

  • 全ての人の名前が M,A,R,C,H のどれかから始まっている
  • 同じ文字から始まる名前を持つ人が複数いない

これらの条件を満たすように 3 人を選ぶ方法が何通りあるか、求めてください。ただし、選ぶ順番は考えません。

答えが 32 bit整数型に収まらない場合に注意してください。

制約

  • 1 \leq N \leq 10^5
  • S_i は英大文字からなる
  • 1 \leq |S_i| \leq 10
  • S_i \neq S_j (i \neq j)

入力

入力は以下の形式で標準入力から与えられる。

N
S_1
:
S_N

出力

与えられた条件を満たすように 3 人を選ぶ方法が x 通りのとき、x を出力せよ。


入力例 1

5
MASHIKE
RUMOI
OBIRA
HABORO
HOROKANAI

出力例 1

2

次のような名前の 3 人を選ぶと良いです。

  • MASHIKE,RUMOI,HABORO

  • MASHIKE,RUMOI,HOROKANAI

よって、2 通りとなります。


入力例 2

4
ZZ
ZZZ
Z
ZZZZZZZZZZ

出力例 2

0

与えられた条件を満たすように 3 人を選ぶ方法が存在しない場合に注意してください。


入力例 3

5
CHOKUDAI
RNG
MAKOTO
AOKI
RINGO

出力例 3

7

Score : 300 points

Problem Statement

There are N people. The name of the i-th person is S_i.

We would like to choose three people so that the following conditions are met:

  • The name of every chosen person begins with M, A, R, C or H.
  • There are no multiple people whose names begin with the same letter.

How many such ways are there to choose three people, disregarding order?

Note that the answer may not fit into a 32-bit integer type.

Constraints

  • 1 \leq N \leq 10^5
  • S_i consists of uppercase English letters.
  • 1 \leq |S_i| \leq 10
  • S_i \neq S_j (i \neq j)

Input

Input is given from Standard Input in the following format:

N
S_1
:
S_N

Output

If there are x ways to choose three people so that the given conditions are met, print x.


Sample Input 1

5
MASHIKE
RUMOI
OBIRA
HABORO
HOROKANAI

Sample Output 1

2

We can choose three people with the following names:

  • MASHIKE, RUMOI, HABORO

  • MASHIKE, RUMOI, HOROKANAI

Thus, we have two ways.


Sample Input 2

4
ZZ
ZZZ
Z
ZZZZZZZZZZ

Sample Output 2

0

Note that there may be no ways to choose three people so that the given conditions are met.


Sample Input 3

5
CHOKUDAI
RNG
MAKOTO
AOKI
RINGO

Sample Output 3

7