PAL5_OOP5/10

package pal;

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

/**
 *
 * @author
 * @date 30.11.2014
 */
public class Main
{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer configuration = new StringTokenizer(br.readLine());
        String alphabet = configuration.nextToken();
        int membersCount = Integer.parseInt(configuration.nextToken());
        int acceptThreshold = Integer.parseInt(configuration.nextToken());
        int proposalLength = Integer.parseInt(configuration.nextToken());

        boolean[] criteriaLengthDistribution = new boolean[10000]; //custom length - just stretch if it doesnt suffice
        Member[] committeeMembers = new Member[membersCount];
        for (int i = 0; i < membersCount; i++) {
            int evaluationCount = Integer.parseInt(br.readLine());
            Set<String> evaluationCriteria = new HashSet<>();
            for (int j = 0; j < evaluationCount; j++) {
                String line = br.readLine();
                criteriaLengthDistribution[line.length()] = true;
                evaluationCriteria.add(line);
            }
            committeeMembers[i] = new Member(evaluationCriteria);
        }

        int minCriteriaLength = 0;
        for (int i = 0; i < criteriaLengthDistribution.length; i++) {
            if (criteriaLengthDistribution[i]) {
                minCriteriaLength = i;
                break;
            }
        }
        Set<String> minCriterias = new HashSet<>();
        for (Member m : committeeMembers) {
            for (String c : m.evaluationList)
                minCriterias.add(c.substring(0, minCriteriaLength));
        }

        Committee committee = new Committee(acceptThreshold, alphabet, criteriaLengthDistribution, committeeMembers);
        BigInteger result = committee.validateAllProposalsDynamic(proposalLength, new ArrayList<String>(minCriterias));

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

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

        public Committee(int acceptThreshold, String alphabet, boolean[] criteriaLengthDistribution, 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);
            this.criteriaLengthDistribution = criteriaLengthDistribution;
        }

        public BigInteger validateAllProposalsDynamic(int maxLen) {
            List<String> startProposals = new LinkedList<>();
            startProposals.add("");
            return validateProposalsDynamic(0, maxLen, BigInteger.ZERO, startProposals);
        }

        public BigInteger validateAllProposalsDynamic(int maxLen, List<String> startProposals) {
            return validateProposalsDynamic(startProposals.get(0).length(), maxLen, BigInteger.ZERO, startProposals);
        }

        private BigInteger validateProposalsDynamic(int curLen, int maxLen, BigInteger carryResult, List<String> carryProposal) {
            if (carryProposal.isEmpty()) { //nothing to carry -> calculate result
                return carryResult.multiply(alphabetSize.pow(maxLen - curLen));
            }
            if (!criteriaLengthDistribution[curLen]) {
                List<String> consideringProposals = new LinkedList<>();
                for (String proposalBase : carryProposal)
                    for (String proposalExtension : alphabetList)
                        consideringProposals.add(proposalBase + proposalExtension);
                return validateProposalsDynamic(curLen + 1, maxLen, carryResult.multiply(alphabetSize), consideringProposals);
            }
            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 validateProposalsDynamic(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 Member(Set<String> evaluationSet) {
            this.evaluationList = evaluationSet;
        }

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

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

}