PAL5_OOP

package pal;

import java.util.*;
import java.math.*;
import java.io.*;

public class Main
{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] configuration = br.readLine().split(" ");
        String alphabet = configuration[0];
        int membersCount = Integer.parseInt(configuration[1]);
        int acceptThreshold = Integer.parseInt(configuration[2]);
        int proposalLength = Integer.parseInt(configuration[3]);

        Member[] committeeMembers = new Member[membersCount];
        for (int i = 0; i < membersCount; i++) {
            committeeMembers[i] = parseMember(br);
        }

        Committee committee = new Committee(acceptThreshold, alphabet, committeeMembers);
        BigInteger result = committee.validateAllProposals(proposalLength);

        System.out.println(result.mod(BigInteger.valueOf(100000)));
    }

    private static Member parseMember(BufferedReader br) throws IOException {
        int evaluationCount = Integer.parseInt(br.readLine());
        String[] evaluationCriteria = new String[evaluationCount];
        for (int i = 0; i < evaluationCount; i++) {
            evaluationCriteria[i] = br.readLine();
        }
        return new Member(evaluationCriteria);
    }

    /***************************************************************************
     *
     */
    public static class Committee
    {
        private final List<Member> memberList;
        private final List<String> alphabetList;
        private final BigInteger alphabetSize;
        private final int acceptThreshold;
        private final int rejectThreshold;

        public Committee(int acceptThreshold, String alphabet, Member... members) {
            this.acceptThreshold = acceptThreshold;
            this.rejectThreshold = members.length - acceptThreshold + 1;
            this.alphabetList = new LinkedList<>();
            this.alphabetSize = BigInteger.valueOf(alphabet.length());
            for (char c : alphabet.toCharArray())
                alphabetList.add(Character.toString(c));
            this.memberList = Arrays.asList(members);
        }

        public BigInteger validateAllProposals(int maxLen) {
            List<String> carryProposal = new LinkedList<>();
            carryProposal.add("");
            return validateAllProposals(1, maxLen, BigInteger.ZERO, carryProposal);
        }

        private BigInteger validateAllProposals(int curLen, int maxLen, BigInteger carryResult, List<String> carryProposal) {
            if (curLen > maxLen) return carryResult; //out of bounds -> result
            List<String> consideringProposals = new LinkedList<>(); //
            BigInteger newResult = BigInteger.ZERO;
            for (String proposalBase : carryProposal) {
                for (String proposalExtension : alphabetList) {
                    String proposal = proposalBase + proposalExtension;
                    //approved proposal
                    int approvedMemberCount = 0;
                    for (Member member : memberList) {
                        if (member.approves(proposal))
                            approvedMemberCount++;
                    }
                    if (approvedMemberCount >= acceptThreshold) {
                        newResult = newResult.add(BigInteger.ONE);
                    }
                    else {
                        //considered proposal
                        int disagreedMemberCount = 0;
                        for (Member member : memberList) {
                            if (!member.considers(proposal))
                                disagreedMemberCount++;
                        }
                        if (disagreedMemberCount < rejectThreshold) {
                            consideringProposals.add(proposal);
                        }
                    }
                }
            }
            return validateAllProposals(curLen + 1, maxLen, carryResult.multiply(alphabetSize).add(newResult), consideringProposals);
        }
    }

    /***************************************************************************
     *
     */
    public static class Member
    {
        private final Set<String> evaluationList;

        public Member(String... evaluationList) {
            this.evaluationList = new HashSet<>(Arrays.asList(evaluationList));
        }

        public boolean considers(String proposal) {
            for (String evalCriteria : evaluationList)
                if (evalCriteria.startsWith(proposal))
                    return true;
            return false;
        }

        public boolean approves(String proposal) {
            for (String evalCriteria : evaluationList)
                if (proposal.startsWith(evalCriteria))
                    return true;
            return false;
        }
    }

}