pal5_STROM

package pal;

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

/**
 *
 * @author zipec
 * @date 2.12.2014
 */
public class Main {
    public static final int MAX_PROPOSAL = 100000;

    public static void main(String[] args) throws IOException {
        //args = new String[]{"pub07.in"};

        BufferedReader br = (args.length == 0)
                ? new BufferedReader(new InputStreamReader(System.in))
                : new BufferedReader(new InputStreamReader(new FileInputStream(args[0])));

        //BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer configuration = new StringTokenizer(br.readLine());
        String alphabet = configuration.nextToken();
        BigInteger alphabetSize = BigInteger.valueOf(alphabet.length());
        int membersCount = Integer.parseInt(configuration.nextToken());
        int acceptThreshold = Integer.parseInt(configuration.nextToken());
        int proposalLength = Integer.parseInt(configuration.nextToken());

        Node tree = new Node();

        //build tree
        for (int i = 0; i < membersCount; i++) {
            int memberCriteriaCount = Integer.parseInt(br.readLine());
            String[] defaultMemberCriteria = new String[memberCriteriaCount];
            for (int j = 0; j < memberCriteriaCount; j++) {
                defaultMemberCriteria[j] = br.readLine();
            }
            criteriaLoop:
            for (String criteria : defaultMemberCriteria) { //for all criterias
                for (String criteriaFilter : defaultMemberCriteria) { //chech against other criterias
                    if (criteriaFilter.length() < criteria.length() && criteria.startsWith(criteriaFilter)) //has prefix criteria
                        continue criteriaLoop; //skips tree.expand
                }
                tree.expandStack(criteria, i); //expand tree with current criteria for current member
            }
        }

        //collection of results
        //  value is depth in tree
        Collection<Integer> results = tree.complyStack(acceptThreshold);

        //aggregate of results
        BigInteger result = countPossibilitiesFromPrefixes(results, alphabetSize, proposalLength);

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

    /***************************************************************************
     * Vrátí součet možných řešení které lze vygenerovat z prefixů v předané množině
     * @param prefixDepths
     * @param alphabetSize
     * @param proposalLength
     * @return
     */
    private static BigInteger countPossibilitiesFromPrefixes(Collection<Integer> prefixDepths, BigInteger alphabetSize, int proposalLength) {
        BigInteger result = BigInteger.ZERO;
        for (int prefixDepth : prefixDepths) {
            result = result.add(
                    BigInteger.ONE.multiply(
                            alphabetSize.pow(proposalLength - prefixDepth)
                    )
            );
        }
        return result;
    }

    /***************************************************************************
     * Uzel stromu
     */
    public static class Node
    {
        public final int depth; //hloubka uzlu
        public final Map<Character,Node> next = new HashMap<>(); //pouzly
        public final Set<Integer> acceptingMembers = new HashSet<>(); //id memberů kteří příjmají podstrom proposalů
        public final Set<Integer> consideringMembers = new HashSet<>(); //id memberů kteří zvažují podstrom proposalů

        public Node() {
            this.depth = 0;
        }

        protected Node(int depth) {
            this.depth = depth;
        }

        /***********************************************************************
         * EXPAND - recurision
         * @param criteria
         * @param memberId
         */
        /*public void expandRecursion(String criteria, int memberId) {
            expandRecursionIteration(criteria.toCharArray(), 0, memberId);
        }

        public void expandRecursionIteration(char[] criteriaPart, int from, int memberId) {
            this.consideringMembers.add(memberId);
            if (criteriaPart.length == from) {
                this.acceptingMembers.add(memberId);
                return;
            }
            Node nextSelected = next.get(criteriaPart[from]);
            if (nextSelected == null) {
                nextSelected = new Node(from + 1);
                next.put(criteriaPart[from], nextSelected);
            }
            nextSelected.expandRecursionIteration(criteriaPart, from + 1, memberId);
        }*/

        /***********************************************************************
         * EXPAND - stack
         * stack pro obejití StackOverflow
         * @param criteria
         * @param memberId
         */
        public void expandStack(String criteria, int memberId) {
            Stack<ExpandIterationTuple> stack = new Stack<>();
            char[] criteriaArr = criteria.toCharArray();
            stack.add(new ExpandIterationTuple(this, 0));
            while (!stack.empty()) {
                ExpandIterationTuple val = stack.pop();
                val.node.expandStackIteration(stack, criteriaArr, val.from, memberId);
            }
        }

        public void expandStackIteration(Stack<ExpandIterationTuple> stack, char[] criteriaPart, int from, int memberId) {
            this.consideringMembers.add(memberId);
            if (criteriaPart.length == from) {
                this.acceptingMembers.add(memberId);
                return;
            }
            Node nextSelected = next.get(criteriaPart[from]);
            if (nextSelected == null) {
                nextSelected = new Node(from + 1);
                next.put(criteriaPart[from], nextSelected);
            }
            stack.add(new ExpandIterationTuple(nextSelected, from + 1));
        }

        /***********************************************************************
         * COMPLY - recursion
         * @param acceptThreshold
         * @return
         */
        /*public Collection<Integer> complyRecursion(int acceptThreshold) {
            return Node.this.complyRecursionIteration(0, acceptThreshold);
        }

        protected Collection<Integer> complyRecursionIteration(int acceptingMembersSoFar, int acceptThreshold) {
            Collection<Integer> result = new LinkedList<>();
            if (acceptingMembers.size() + acceptingMembersSoFar >= acceptThreshold) {
                result.add(depth);
            }
            else if (consideringMembers.size() + acceptingMembersSoFar >= acceptThreshold) {
                for (Node nextOne : next.values()) {
                    result.addAll(nextOne.complyRecursionIteration(acceptingMembers.size() + acceptingMembersSoFar, acceptThreshold));
                }
            }
            return result;
        }*/

        /***********************************************************************
         * COMPLY - stack
         * stack pro obejití StackOverflow
         * @param acceptThreshold
         * @return
         */
        public Collection<Integer> complyStack(int acceptThreshold) {
            Collection<Integer> result = new LinkedList<>();
            Stack<ComplyIterationTuple> stack = new Stack<>();
            stack.push(new ComplyIterationTuple(this, 0));
            while (!stack.empty()) {
                ComplyIterationTuple val = stack.pop();
                val.node.complyStackIteration(result, stack, val.results, acceptThreshold);
            }
            return result;
        }

        protected void complyStackIteration(Collection<Integer> result, Stack<ComplyIterationTuple> stack, int acceptingMembersSoFar, int acceptThreshold) {
            if (acceptingMembers.size() + acceptingMembersSoFar >= acceptThreshold) {
                result.add(depth);
            }
            else if (consideringMembers.size() + acceptingMembersSoFar >= acceptThreshold) {
                for (Node nextOne : next.values()) {
                    stack.add(new ComplyIterationTuple(nextOne, acceptingMembers.size() + acceptingMembersSoFar));
                }
            }
        }
    }

    /***************************************************************************
     * Helper class - Tuple
     */
    public static class ComplyIterationTuple
    {
        public final Node node;
        public final int results;

        public ComplyIterationTuple(Node node, int results) {
            this.node = node;
            this.results = results;
        }
    }

    /***************************************************************************
     * Helper class - Tuple
     */
    public static class ExpandIterationTuple
    {
        public final Node node;
        public final int from;

        public ExpandIterationTuple(Node node, int from) {
            this.node = node;
            this.from = from;
        }
    }
}