Shared code

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

public class Main {

    private static final int MOD = 1000000007;

    public static void main(String[] args) throws IOException {
        InputReader sc = new InputReader();
        PrintWriter out = new PrintWriter(System.out);

        String s = sc.next();
        int k = sc.nextInt();

        Trie root = new Trie();
        while (k-- > 0) {
            root.insert(sc.next());
        }

        int n = s.length();
        long[] dp = new long[n + 1];
        dp[0] = 1; // Base case: one way to form an empty string

        for (int i = 0; i < n; i++) {
            Trie node = root;
            for (int j = i; j < n; j++) {
                node = node.get(s.charAt(j));
                if (node == null) break;
                if (node.isEnd()) {
                    dp[j + 1] = (dp[j + 1] + dp[i]) % MOD;
                }
            }
        }

        out.println(dp[n]);
        out.close();
    }

    static class Trie {
        Trie[] children;
        boolean end;

        Trie() {
            children = new Trie[26];
            end = false;
        }

        void insert(String word) {
            Trie node = this;
            for (char c : word.toCharArray()) {
                int index = c - 'a';
                if (node.children[index] == null) {
                    node.children[index] = new Trie();
                }
                node = node.children[index];
            }
            node.end = true;
        }

        Trie get(char c) {
            return children[c - 'a'];
        }

        boolean isEnd() {
            return end;
        }
    }

    static class InputReader {
        private StringTokenizer st;
        private BufferedReader bf;

        public InputReader() {
            bf = new BufferedReader(new InputStreamReader(System.in));
        }

        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens()) {
                st = new StringTokenizer(bf.readLine());
            }
            return st.nextToken();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
    }
}