Basic Committee Work Model

A committee is an assembly of some number of members whose job is to evaluate proposals and subsequently accept or reject them. A proposal is an unempty string over a finite alphabet A. The alphabet is the same for all proposals.
Each committee member is equipped with his/her own so called evaluation list of strings over A. A proposal is accepted by a committe member if and only if some unempty prefix of the proposal is equal to some string in the evaluation list of that committe member.
Let N be the number of committee members and let D be a fixed integer with the property 1 ≤ D ≤ N. Any proposal is evaluated by each committee member and it is accepted by the committee if and only if at least D committee members accept it.

The task

You are given the the alphabet A of the proposals, the value of D, a positive integer K and the evaluation lists of all committee members.
Determine the number of all possible proposals of length K which are accepted by the committee.

---

Input

The input contains several text lines. The first line contains unempty string SA followed by space and three integers N, D, K separated by spaces. The string SA represents the alphabet A, it consists of lowercase letters, no letter is repeated in SA. N is the number of committee members, D is minimum number of committee members which must accept a proposal in order for that proposal to be accepted by the committee, K is a positive integer.
Next, there are N evaluation lists belonging to respective commitee members. Each list starts with a line containing single positive integer representing the length of that list. Next, there is the same number of lines, each contains one unempty string over A. Note that strings may be repeated in the list.
It holds that 2 ≤ |SA| ≤ 26, 1 ≤ D ≤ N ≤ 10⁵, 1 ≤ K ≤ 100000. No list element is longer than 100000 characters.
The total nuber of characters in all evaluation lists taken together does not exceed 2×10⁷.

Output

The output contains one text line with one integer representing the number of all possible proposals of length K which are accepted by the committee. The number is printed modulo 100000.

Example 1

Input

abcd 3 2 5
2
abcd
dcba
3
abc
abc
dcba
4
abcd
abc
abcd
aba

Output

20

All proposals accepted by the committee in Example 1 are:

abcaa  abcba  abcca  abcda  dcbaa
abcab  abcbb  abccb  abcdb  dcbab
abcac  abcbc  abccc  abcdc  dcbac
abcad  abcbd  abccd  abcdd  dcbad

Example 2

Input

uvwxyz 2 2 4
2
uv
wxyz
2
vu
zwyx

Output

0

There can be no proposal accepted by the committee in Example 2.

Example 3

Input

klmnoprstu 2 1 111
1
tt
2
kk
ms

Output

0

There are 3×10¹⁰⁹ proposals of length 111 accepted by the committee in Example 3.

Example 4

Input

abcde 5 1 15
1
a
2
ba
bbb
3
caaa
cbbbb
cccccc
4
daaaaaa
dbbbbbbb
dcccccccc
dddddddddd
5
eaaaaaaaaaa
ebbbbbbbbbbb
ecccccccccccc
eddddddddddddd
eeeeeeeeeeeeeee

Output

94531

There are ¼ × (5¹⁵ −1) = 7629394531 proposals of length 15 accepted by the committee in Example 4.

---

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set