Princess Asseylum Vers Allusia needs to send a party invitation to her father, King Rayregalia Vers Rayvers on Mars! However, she cannot send the invitation in plain text, because enemies are intercepting messages at the moon base. Therefore, Princess Asseylum decided to encrypt her message by concatenating all of the Martian words in her message together to form one long string. The encrypted message is a string ~S~ ~(1 \le |S| \le 2\,000)~ made up of lowercase letters from a to z.

When King Rayregalia received the invitation, he took out his dictionary of ~N~ ~(1 \le N \le 2\,000)~ Martian words, all different, each containing at most ~2\,000~ lowercase letters from a to z. Unfortunately, King Rayregalia is getting old, and in his bedridden state he is unable to understand what his daughter is trying to convey because when he looks at the invitation, all he can think about is that the substrings of it look like they also contain important information! A substring is important if and only if it is created by concatenating one or more Martian words together (repeats are allowed). Since there are an overwhelming number of substrings for King Rayregalia to check manually, he has hired you to advise him on the number of important substrings of Princess Asseylum's invitation.

Constraints

• In test cases worth 25% of points, ~1 \le |S| \le 50~ and ~1 \le N \le 7~.
• In test cases worth another 25% of points, ~1 \le |S| \le 100~ and ~1 \le N \le 100~.
• In test cases worth another 25% of points, ~1 \le |S| \le 500~.
• In the rest of the test cases, the constraints given in the problem statement will hold.

Input Specification

The first line of input will have ~S~.

The second line of input will have ~N~.

The next ~N~ lines of input will each have a word in King Rayregalia's dictionary.

Output Specification

A single line containing the number of important substrings.

Sample Input 1

dearfather
2
dear
father

Sample Output 1

3

Sample Input 2

iamwritingfromearthtoinformyouofmysituation
7
a
i
my
to
of
it
earth

Sample Output 2

22

Sample Input 3

itspartytime
3
its
party
time

Sample Output 3

6