DPS

Interview

Time limit1sMemory limit1024 MB

Summary

Count the unordered groups of three people whose handle initials can be rearranged to spell the team name S.

Level: Easy3 of 10
Topics: Combinatorics, Math, Hash map
Solved: No attempts yet

Problem

ICPC is an international collegiate programming contest where each team has three members. The name of each team is formed by joining the first letters of the three members' handles in any order. A handle is a unique ID used on online judge sites.

For example, if the handles are DONGGAS, PICASSO, and SEMTEO, the team name is one of DPS, DSP, PDS, PSD, SDP, or SPD. If the handles are RAARARAARA, WBCHO, and WEASEL, the team name is one of RWW, WRW, or WWR.

Given a team name $S$ and the handles of $N$ people, count all the ways to form the team $S$ from those $N$ people.

Input

The first line contains the team name $S$ , which consists of three uppercase English letters.

The second line contains a positive integer $N$ ( $3 \le N \le 50\,000$ ), the number of people.

From the third line, $N$ handles are given, one per line. The length of each handle is between 1 and 10.

Each handle is a string of uppercase English letters with no spaces. All handles are distinct.

Output

Print the number of ways to form the team $S$ from the given people.

The answer may exceed the range of a 32-bit integer, so use a 64-bit integer type for your language:

C/C++: long long
Java: long
Kotlin: Long

Examples3

Example 1

Input

DPS
7
DONGGAS
PICASSO
SEMTEO
DJS
WBCHO
RAARARAARA
WEASEL

Expected output

Example 2
Input
```
DDD
4
DONGGAS
DJS
DURAM
DART
```
Expected output
```
4
```

Example 3

Input

SGS
4
GUMGOOD
SHIFTPSH
SHANDY
SANGPIL

Expected output