#include <bits/stdc++.h>
using namespace std;

// ===================================================================
// This file provides two Aho‑Corasick implementations:
//   1) SimpleAhoCorasick  – memory‑efficient, only total match counts
//   2) AdvancedAhoCorasick – full per‑pattern counts, distinct patterns,
//      longest pattern, replacement, and DP helpers.
//
// Read the comments above each struct and its methods to understand:
//   - What it solves
//   - Input / output
//   - Time complexity
//   - Preconditions
// ===================================================================

const int ALPHABET = 26;  // only lowercase 'a'..'z' is supported

// ===================================================================
// 1) SIMPLE AHO‑CORASICK (total matches only)
// ===================================================================
// Purpose:
//   Build a trie from patterns and compute failure links.
//   Provides fast scanning to count total occurrences of *any* pattern.
// Memory:
//   O(total_length_of_patterns) nodes.
// Each node stores:
//   - next[ALPHABET] : transitions (pre‑computed after build)
//   - fail           : failure link
//   - out            : number of patterns ending exactly at this node
//   - output_link    : nearest node in the fail‑chain that has out>0
//   - depth          : depth in the trie (used for longest match)
// ===================================================================

struct SimpleAhoCorasick {
    vector<array<int, ALPHABET>> next;
    vector<int> fail, out, output_link, depth;

    SimpleAhoCorasick() {
        // root = state 0
        next.push_back({});
        fail.push_back(0);
        out.push_back(0);
        output_link.push_back(0);
        depth.push_back(0);
    }

    // Add one pattern (multiple identical patterns are allowed – out counts them).
    void addPattern(const string &s) {
        int node = 0;
        for (char c : s) {
            int idx = c - 'a';
            if (!next[node][idx]) {
                next[node][idx] = next.size();
                next.push_back({});
                fail.push_back(0);
                out.push_back(0);
                output_link.push_back(0);
                depth.push_back(depth[node] + 1);
            }
            node = next[node][idx];
        }
        out[node]++;
    }

    // Build failure links and pre‑compute transitions.
    // Must be called after all patterns are added and before any search.
    void build() {
        queue<int> q;
        // depth 1 nodes: failure goes to root
        for (int c = 0; c < ALPHABET; ++c) {
            int child = next[0][c];
            if (child) {
                fail[child] = 0;
                q.push(child);
            }
        }

        while (!q.empty()) {
            int v = q.front();
            q.pop();

            // Set output_link for v: if out[v]>0 then v itself, else follow fail's output_link.
            if (out[v]) output_link[v] = v;
            else output_link[v] = output_link[fail[v]];

            for (int c = 0; c < ALPHABET; ++c) {
                int u = next[v][c];
                if (u) {
                    fail[u] = next[fail[v]][c];
                    q.push(u);
                } else {
                    // Pre‑compute missing transitions for speed.
                    next[v][c] = next[fail[v]][c];
                }
            }
        }
    }

    // 1.1) Total number of occurrences of any pattern in the text.
    //      Overlapping matches are counted separately.
    //      Complexity: O(|text| + total_matches) in worst case.
    long long countTotalMatches(const string &text) const {
        long long ans = 0;
        int state = 0;
        for (char c : text) {
            state = next[state][c - 'a'];
            // Traverse the output‑link chain to add all patterns ending here.
            for (int v = output_link[state]; v != 0; v = output_link[fail[v]]) {
                ans += out[v];
            }
        }
        return ans;
    }

    // 1.2) Find the earliest ending index (0‑based) where any pattern appears.
    //      Returns -1 if none.
    //      Complexity: O(|text|).
    int firstMatchEnd(const string &text) const {
        int state = 0;
        for (int i = 0; i < (int)text.size(); ++i) {
            state = next[state][text[i] - 'a'];
            if (output_link[state] != 0) return i;  // at least one pattern ends at i
        }
        return -1;
    }

    // 1.3) Check whether any pattern appears in the text.
    //      Complexity: O(|text|) with early exit.
    bool containsAny(const string &text) const {
        int state = 0;
        for (char c : text) {
            state = next[state][c - 'a'];
            if (output_link[state] != 0) return true;
        }
        return false;
    }

    // 1.4) For each position i, get the length of the longest pattern that ends at i.
    //      Returns a vector of length |text|, where 0 means no pattern ends there.
    //      Complexity: O(|text|).
    vector<int> longestPatternLengthAtEachPos(const string &text) const {
        vector<int> res(text.size(), 0);
        int state = 0;
        for (int i = 0; i < (int)text.size(); ++i) {
            state = next[state][text[i] - 'a'];
            int v = output_link[state];
            if (v) res[i] = depth[v];   // deepest output node = longest pattern
        }
        return res;
    }
};

// ===================================================================
// 2) ADVANCED AHO‑CORASICK (full per‑pattern support)
// ===================================================================
// Purpose:
//   Same as simple, but stores the ID(s) of patterns ending at each node.
//   Enables per‑pattern counts, distinct patterns, replacement,
//   DP for counting strings without patterns, etc.
// Memory:
//   O(total_length_of_patterns + total_number_of_patterns).
// ===================================================================

struct AdvancedAhoCorasick {
    vector<array<int, ALPHABET>> next;
    vector<int> fail, depth, output_link;
    vector<vector<int>> pattern_ids;   // list of pattern indices that end at this node

    AdvancedAhoCorasick() {
        next.push_back({});
        fail.push_back(0);
        depth.push_back(0);
        output_link.push_back(0);
        pattern_ids.push_back({});
    }

    // Add a pattern with a given ID (usually its index in the input list).
    void addPattern(const string &s, int id) {
        int node = 0;
        for (char c : s) {
            int idx = c - 'a';
            if (!next[node][idx]) {
                next[node][idx] = next.size();
                next.push_back({});
                fail.push_back(0);
                depth.push_back(depth[node] + 1);
                output_link.push_back(0);
                pattern_ids.push_back({});
            }
            node = next[node][idx];
        }
        pattern_ids[node].push_back(id);
    }

    // Build failure links and pre‑compute transitions.
    void build() {
        queue<int> q;
        for (int c = 0; c < ALPHABET; ++c) {
            int child = next[0][c];
            if (child) {
                fail[child] = 0;
                q.push(child);
            }
        }

        while (!q.empty()) {
            int v = q.front();
            q.pop();

            if (!pattern_ids[v].empty()) output_link[v] = v;
            else output_link[v] = output_link[fail[v]];

            for (int c = 0; c < ALPHABET; ++c) {
                int u = next[v][c];
                if (u) {
                    fail[u] = next[fail[v]][c];
                    q.push(u);
                } else {
                    next[v][c] = next[fail[v]][c];
                }
            }
        }
    }

    // 2.1) Count occurrences of each pattern in the text.
    //      Returns a vector of length total_patterns.
    //      Complexity: O(|text| + total_matches).
    vector<int> countOccurrences(const string &text, int total_patterns) const {
        vector<int> ans(total_patterns, 0);
        int state = 0;
        for (char c : text) {
            state = next[state][c - 'a'];
            for (int v = output_link[state]; v != 0; v = output_link[fail[v]]) {
                for (int id : pattern_ids[v]) {
                    ans[id]++;
                }
            }
        }
        return ans;
    }

    // 2.2) Count how many distinct patterns appear at least once.
    //      Complexity: O(|text| + total_matches).
    int countDistinctPatterns(const string &text, int total_patterns) const {
        vector<char> seen(total_patterns, 0);
        int distinct = 0;
        int state = 0;
        for (char c : text) {
            state = next[state][c - 'a'];
            for (int v = output_link[state]; v != 0; v = output_link[fail[v]]) {
                for (int id : pattern_ids[v]) {
                    if (!seen[id]) {
                        seen[id] = 1;
                        distinct++;
                    }
                }
            }
        }
        return distinct;
    }

    // 2.3) For each position i, get the length and ID of the longest pattern ending at i.
    //      Returns two vectors: lengths and IDs (‑1 if none).
    //      Complexity: O(|text|).
    pair<vector<int>, vector<int>> longestPatternAtEachPos(const string &text) const {
        int n = text.size();
        vector<int> len(n, 0), id(n, -1);
        int state = 0;
        for (int i = 0; i < n; ++i) {
            state = next[state][text[i] - 'a'];
            int v = output_link[state];
            if (v) {
                len[i] = depth[v];
                id[i] = pattern_ids[v][0];   // all patterns at this node have same length
            }
        }
        return {len, id};
    }

    // 2.4) Replace all occurrences of any pattern with a replacement string.
    //      Longest match is chosen when overlaps occur.
    //      Complexity: O(|text| + total_replacement_length).
    string replaceOccurrences(const string &text, const string &replacement) const {
        auto [len_arr, id_arr] = longestPatternAtEachPos(text);
        string res;
        int i = 0;
        while (i < (int)text.size()) {
            if (len_arr[i] > 0) {
                res += replacement;
                i += len_arr[i];
            } else {
                res += text[i];
                i++;
            }
        }
        return res;
    }

    // 2.5) Find all starting positions of occurrences of a specific pattern (by ID).
    //      Returns a vector of start indices (0‑based).
    //      Complexity: O(|text| + occurrences_of_target).
    vector<int> findOccurrencesOfPattern(const string &text, int target_id) const {
        vector<int> positions;
        int state = 0;
        for (int i = 0; i < (int)text.size(); ++i) {
            state = next[state][text[i] - 'a'];
            for (int v = output_link[state]; v != 0; v = output_link[fail[v]]) {
                for (int id : pattern_ids[v]) {
                    if (id == target_id) {
                        positions.push_back(i - depth[v] + 1);
                    }
                }
            }
        }
        return positions;
    }
};

// ===================================================================
// 3) COMMON CONTEST TRICKS (ECPC / ACPC style)
// ===================================================================

// 3.1) Count substrings that contain NO pattern (all substrings are "good").
//      For each right endpoint R, find the leftmost L such that [L..R] contains no pattern.
//      Complexity: O(|text| + total_matches) (if using output‑link chain).
long long countGoodSubstrings(const string &text, const AdvancedAhoCorasick &ac) {
    int n = text.size();
    long long ans = 0;
    int state = 0;
    int last_bad = -1;   // rightmost ending position of a pattern seen so far

    for (int i = 0; i < n; ++i) {
        state = ac.next[state][text[i] - 'a'];
        // If any pattern ends at i, update last_bad.
        if (ac.output_link[state] != 0) {
            last_bad = i;
        }
        // All substrings ending at i with start > last_bad are good.
        ans += (i - last_bad);
    }
    return ans;
}

// 3.2) Count strings of length N over the alphabet that contain NO pattern.
//      Uses DP on the automaton.
//      Complexity: O(N * states * ALPHABET).
long long countStringsWithoutPatterns(int N, const AdvancedAhoCorasick &ac, long long MOD = 1e9+7) {
    int S = ac.next.size();
    vector<char> bad(S, 0);
    // Mark a state as bad if any pattern ends at it or along its fail‑chain.
    for (int v = 0; v < S; ++v) {
        int u = v;
        while (u) {
            if (!ac.pattern_ids[u].empty()) {
                bad[v] = 1;
                break;
            }
            u = ac.fail[u];
        }
    }

    vector<vector<long long>> dp(N+1, vector<long long>(S, 0));
    dp[0][0] = 1;   // empty string at root
    for (int len = 0; len < N; ++len) {
        for (int state = 0; state < S; ++state) {
            if (bad[state] || dp[len][state] == 0) continue;
            for (int c = 0; c < ALPHABET; ++c) {
                int nxt = ac.next[state][c];
                if (!bad[nxt]) {
                    dp[len+1][nxt] = (dp[len+1][nxt] + dp[len][state]) % MOD;
                }
            }
        }
    }

    long long ans = 0;
    for (int state = 0; state < S; ++state) {
        if (!bad[state]) ans = (ans + dp[N][state]) % MOD;
    }
    return ans;
}

// 3.3) Count strings of length N that contain AT LEAST ONE pattern.
//      (Total strings - those with no pattern)
long long countStringsWithAtLeastOnePattern(int N, const AdvancedAhoCorasick &ac, long long MOD = 1e9+7) {
    long long total = 1;
    for (int i = 0; i < N; ++i) total = (total * ALPHABET) % MOD;
    long long no = countStringsWithoutPatterns(N, ac, MOD);
    return (total - no + MOD) % MOD;
}

// 3.4) Find the length of the longest pattern that appears in the text.
//      Returns {length, pattern_id} (‑1 if none).
pair<int,int> longestPatternInText(const string &text, const AdvancedAhoCorasick &ac) {
    int state = 0;
    int best_len = 0, best_id = -1;
    for (char c : text) {
        state = ac.next[state][c - 'a'];
        for (int v = ac.output_link[state]; v != 0; v = ac.output_link[ac.fail[v]]) {
            if (!ac.pattern_ids[v].empty()) {
                int len = ac.depth[v];
                if (len > best_len) {
                    best_len = len;
                    best_id = ac.pattern_ids[v][0];
                }
            }
        }
    }
    return {best_len, best_id};
}

// ===================================================================
// 4) HELPER: build an AdvancedAhoCorasick from a vector of patterns
// ===================================================================

AdvancedAhoCorasick buildAC(const vector<string>& patterns) {
    AdvancedAhoCorasick ac;
    for (int i = 0; i < (int)patterns.size(); ++i) {
        ac.addPattern(patterns[i], i);
    }
    ac.build();
    return ac;
}

// ===================================================================
// EXAMPLE USAGE (can be removed)
// ===================================================================

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<string> patterns = {"he", "she", "his", "hers"};
    AdvancedAhoCorasick ac = buildAC(patterns);

    string text = "ushers";
    auto counts = ac.countOccurrences(text, patterns.size());
    cout << "Occurrences:\n";
    for (int i = 0; i < (int)patterns.size(); ++i) {
        cout << patterns[i] << ": " << counts[i] << "\n";
    }

    cout << "Distinct patterns: " << ac.countDistinctPatterns(text, patterns.size()) << "\n";

    auto [len_arr, id_arr] = ac.longestPatternAtEachPos(text);
    cout << "Longest pattern ending at each position:\n";
    for (int i = 0; i < (int)text.size(); ++i) {
        cout << i << ": len=" << len_arr[i] << ", id=" << id_arr[i] << "\n";
    }

    string replaced = ac.replaceOccurrences(text, "[MASK]");
    cout << "Replaced text: " << replaced << "\n";

    long long good = countGoodSubstrings(text, ac);
    cout << "Number of substrings with no pattern: " << good << "\n";

    return 0;
}