|
You are given a string S, consisting of lowercase Latin letters.
The length of string is L. There are N small strings. You
should concatenate all of them in any order to get string T. Your
task is to count the number of different strings T, which are
subsequences of string S.
Input
The first line contains L lowercase Latin letters (1 ≤ L
≤ 10000). The second line contains integer N (1 ≤ N ≤ 9)
- the number of small strings, which should be concatenated. The following
N lines contain sequences of lowercase Latin letters. The total
length of small strings does not exceed 1000 symbols.
Output
Output a single number - the answer for the problem.
|
|
Input 1
|
Output 1
|
abracadabra
2
aaa
a
|
1
|
|
Input 2
|
Output 2
|
abracadabra
2
ara
bra
|
2
|
|