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

using ll = long long;

// =======================================================================
// DEFINITIONS (read this first)
// =======================================================================
//
// - Prefix: a substring that starts at index 0.
// - Proper prefix: a prefix that is NOT equal to the whole string.
// - Suffix: a substring that ends at the last index.
// - Border: a string that is both a prefix and a suffix.
//   Example: in "abcab", "ab" is a border.
// - pi[i]: length of the longest proper border of the prefix ending at i.
//   This is the core of KMP.
// - State in KMP: the length of the longest prefix of the pattern that is
//   a suffix of the processed text.
// - Period: a positive integer p such that the string can be formed by
//   repeating its prefix of length p.
// =======================================================================

// =======================================================================
// 1) Prefix Function (pi) – the heart of KMP
// =======================================================================

// buildPrefixFunction
// --------------------
// What it does:
//   Computes the prefix function (pi array) for a given pattern.
//   pi[i] = length of the longest proper prefix of pattern[0..i]
//   that is also a suffix of pattern[0..i].
//
// Input:
//   pattern: a string (or vector, see generic section).
//
// Output:
//   vector<int> pi, size = pattern.size().
//   pi[0] is always 0.
//
// Time complexity: O(m) where m = pattern.size().
//
// Constraints:
//   pattern must not be empty (returns empty vector if empty).
//
// Notes:
//   You rarely call this directly; it is used internally by all KMP functions.
vector<int> buildPrefixFunction(const string& p) {
    int m = (int)p.size();
    vector<int> pi(m, 0);
    for (int i = 1; i < m; ++i) {
        int j = pi[i - 1];
        while (j > 0 && p[i] != p[j]) j = pi[j - 1];
        if (p[i] == p[j]) ++j;
        pi[i] = j;
    }
    return pi;
}

// =======================================================================
// 2) Basic Pattern Search
// =======================================================================

// kmpSearch
// ----------
// What it does:
//   Finds all starting positions (0-indexed) where 'pattern' occurs
//   inside 'text'. Overlapping occurrences are both reported.
//
// Input:
//   text: the string to search in.
//   pattern: the string to search for.
//
// Output:
//   vector<int> positions: each position is the start index of an occurrence.
//   If pattern does not occur, the vector is empty.
//
// Time complexity: O(n + m) where n = text.size(), m = pattern.size().
//
// Constraints:
//   pattern must not be empty. If pattern is empty, the behaviour is undefined
//   (we return empty vector).
//
// Notes:
//   This is the standard KMP search. Overlapping is allowed.
vector<int> kmpSearch(const string& text, const string& pattern) {
    vector<int> res;
    int n = (int)text.size(), m = (int)pattern.size();
    if (m == 0) return res;
    vector<int> pi = buildPrefixFunction(pattern);
    int j = 0;
    for (int i = 0; i < n; ++i) {
        while (j > 0 && text[i] != pattern[j]) j = pi[j - 1];
        if (text[i] == pattern[j]) ++j;
        if (j == m) {
            res.push_back(i - m + 1);
            j = pi[j - 1];  // allow overlapping
        }
    }
    return res;
}

// =======================================================================
// 3) Counting Occurrences
// =======================================================================

// countOverlapping
// -----------------
// What it does:
//   Counts how many times 'pattern' appears in 'text' allowing overlaps.
//
// Input:
//   text, pattern: strings.
//
// Output:
//   int: number of overlapping occurrences.
//
// Time complexity: O(n + m).
//
// Constraints: pattern must not be empty.
//
// Notes: simply returns kmpSearch(text, pattern).size().
int countOverlapping(const string& text, const string& pattern) {
    return (int)kmpSearch(text, pattern).size();
}

// countNonOverlapping
// --------------------
// What it does:
//   Counts the maximum number of occurrences of 'pattern' in 'text'
//   such that no two occurrences overlap.
//
// Input:
//   text, pattern: strings.
//
// Output:
//   int: maximum number of non-overlapping occurrences.
//
// Time complexity: O(n + m).
//
// Constraints: pattern must not be empty.
//
// Notes:
//   Uses a greedy approach: take the leftmost occurrence, then the next
//   one that starts after it ends.
int countNonOverlapping(const string& text, const string& pattern) {
    vector<int> pos = kmpSearch(text, pattern);
    if (pos.empty()) return 0;
    int cnt = 1;
    int last = pos[0];
    int m = (int)pattern.size();
    for (int i = 1; i < (int)pos.size(); ++i) {
        if (pos[i] >= last + m) {
            ++cnt;
            last = pos[i];
        }
    }
    return cnt;
}

// =======================================================================
// 4) Borders and Periodicity
// =======================================================================

// longestBorder
// --------------
// What it does:
//   Returns the length of the longest proper border of the whole pattern.
//   That is pi[m-1].
//
// Input:
//   pattern: string.
//
// Output:
//   int: length of longest border.
//
// Time complexity: O(m) (builds prefix function).
//
// Constraints: pattern not empty.
//
// Notes:
//   If pattern has no border, returns 0.
int longestBorder(const string& pattern) {
    vector<int> pi = buildPrefixFunction(pattern);
    return pi.empty() ? 0 : pi.back();
}

// allBorders
// -----------
// What it does:
//   Returns all lengths of borders of the pattern, from longest to shortest.
//
// Input:
//   pattern: string.
//
// Output:
//   vector<int> border lengths, excluding 0.
//
// Time complexity: O(m).
//
// Constraints: pattern not empty.
//
// Notes:
//   Example: pattern = "ababa" → borders: "aba" (3), "a" (1) → returns [3,1].
vector<int> allBorders(const string& pattern) {
    vector<int> pi = buildPrefixFunction(pattern);
    vector<int> borders;
    int len = pi.back();
    while (len > 0) {
        borders.push_back(len);
        len = pi[len - 1];
    }
    return borders;
}

// smallestPeriod
// ---------------
// What it does:
//   Finds the smallest period p such that the string consists of repetitions
//   of its prefix of length p.
//
// Input:
//   s: string.
//
// Output:
//   int: the smallest period length. If no period smaller than n, returns n.
//
// Time complexity: O(n).
//
// Constraints: s not empty.
//
// Notes:
//   Example: "ababab" → period = 2.
//   Uses: period = n - pi[n-1]; if n % period == 0, answer is period.
int smallestPeriod(const string& s) {
    int n = (int)s.size();
    vector<int> pi = buildPrefixFunction(s);
    int period = n - pi[n - 1];
    if (n % period == 0) return period;
    return n;
}

// isPeriodic
// -----------
// What it does:
//   Checks if the string is made of repetitions of a smaller block.
//
// Input:
//   s: string.
//
// Output:
//   bool: true if s is periodic (period < n), false otherwise.
//
// Time complexity: O(n).
bool isPeriodic(const string& s) {
    return smallestPeriod(s) < (int)s.size();
}

// =======================================================================
// 5) KMP Automaton (Deterministic Finite Automaton)
// =======================================================================

// buildKMPAutomaton
// ------------------
// What it does:
//   Builds a transition table for the KMP automaton of a fixed pattern.
//   The automaton has states 0..m where m = pattern.size().
//   State 0: no prefix matched. State m: pattern matched completely.
//   For each state and each character, it gives the next state after reading
//   that character.
//
// Input:
//   pattern: a lowercase English string.
//   alphabetSize: number of distinct characters, default 26 (a..z).
//
// Output:
//   vector<vector<int>> automaton of size (m+1) x alphabetSize.
//   automaton[state][c] = next state (0..m).
//
// Time complexity: O(m * alphabetSize).
//
// Constraints:
//   - Works for lowercase English letters only.
//   - If you need another alphabet, change the character mapping inside.
//
// Notes:
//   This automaton is useful for DP problems (e.g., counting strings that
//   avoid a pattern) or for fast repeated searching.
//   The transition from state m (full match) is defined using the fallback
//   of the last character, which is standard for continued matching.
vector<vector<int>> buildKMPAutomaton(const string& pattern, int alphabetSize = 26) {
    int m = (int)pattern.size();
    vector<vector<int>> aut(m + 1, vector<int>(alphabetSize, 0));
    if (m == 0) return aut;  // not meaningful
    vector<int> pi = buildPrefixFunction(pattern);

    for (int state = 0; state <= m; ++state) {
        for (int c = 0; c < alphabetSize; ++c) {
            if (state < m && c == pattern[state] - 'a') {
                aut[state][c] = state + 1;
            } else if (state == 0) {
                aut[state][c] = 0;
            } else {
                aut[state][c] = aut[pi[state - 1]][c];
            }
        }
    }
    return aut;
}

// =======================================================================
// 6) DP with KMP Automaton
// =======================================================================

// countStringsAvoidPattern
// -------------------------
// What it does:
//   Counts the number of strings of a given length over an alphabet of size
//   'alphabetSize' that do NOT contain 'pattern' as a substring.
//
// Input:
//   len: length of the strings to count.
//   pattern: the forbidden pattern (lowercase English).
//   alphabetSize: number of letters (e.g., 2 for binary, 26 for English).
//   MOD: modulo value (use 1e9+7 or similar).
//
// Output:
//   long long: count modulo MOD.
//
// Time complexity: O(len * m * alphabetSize), where m = pattern.size().
//
// Constraints:
//   pattern must not be empty. alphabetSize should be ≤ 26 if using default
//   buildKMPAutomaton. For larger alphabets, adapt the automaton.
//
// Notes:
//   This is a classic DP on KMP automaton. You can also count strings that
//   contain the pattern at least once by subtracting from total.
ll countStringsAvoidPattern(int len, const string& pattern, int alphabetSize, ll MOD) {
    int m = (int)pattern.size();
    if (m == 0) return 0;  // undefined
    vector<vector<int>> aut = buildKMPAutomaton(pattern, alphabetSize);
    vector<vector<ll>> dp(len + 1, vector<ll>(m + 1, 0));
    dp[0][0] = 1;
    for (int i = 0; i < len; ++i) {
        for (int state = 0; state < m; ++state) {  // avoid state m (match)
            if (dp[i][state] == 0) continue;
            for (int c = 0; c < alphabetSize; ++c) {
                int ns = aut[state][c];
                if (ns == m) continue;  // would contain pattern, skip
                dp[i + 1][ns] = (dp[i + 1][ns] + dp[i][state]) % MOD;
            }
        }
    }
    ll ans = 0;
    for (int state = 0; state < m; ++state) {
        ans = (ans + dp[len][state]) % MOD;
    }
    return ans;
}

// =======================================================================
// 7) Advanced Tricks (appeared in ECPC / ACPC)
// =======================================================================

// prefixOccurrences
// ------------------
// What it does:
//   For each prefix length i (1..m) of the pattern, count how many times
//   that prefix appears as a substring inside the text.
//
// Input:
//   text, pattern: strings.
//
// Output:
//   vector<int> cnt of size m+1, where cnt[i] = number of occurrences of
//   pattern[0..i-1] in text.
//   cnt[0] is meaningless (ignore it).
//
// Time complexity: O(n + m).
//
// Constraints: pattern not empty.
//
// Notes:
//   This uses a well-known trick: during KMP search, increment cnt[state] for
//   each position; then propagate counts through the border links.
//   Example: text = "aaaa", pattern = "aa" → cnt[1]=3, cnt[2]=3? Actually
//   prefix "a" appears 4 times? The function counts substrings of length i,
//   so "a" appears 4 times, "aa" appears 3 times. Let's test.
vector<int> prefixOccurrences(const string& text, const string& pattern) {
    int m = (int)pattern.size();
    vector<int> cnt(m + 1, 0);
    if (m == 0) return cnt;
    vector<int> pi = buildPrefixFunction(pattern);
    int j = 0;
    for (char c : text) {
        while (j > 0 && c != pattern[j]) j = pi[j - 1];
        if (c == pattern[j]) ++j;
        cnt[j]++;           // state j was reached
        if (j == m) {
            j = pi[j - 1];  // fall back for overlapping
        }
    }
    // Propagate counts through the border tree
    for (int i = m; i >= 1; --i) {
        cnt[pi[i - 1]] += cnt[i];
    }
    return cnt;  // cnt[0] is ignored
}

// removeOccurrences
// ------------------
// What it does:
//   Removes all occurrences of 'pattern' from 'text'. After a removal,
//   the remaining parts are concatenated, which may form new occurrences.
//   This function repeatedly removes until no occurrence remains.
//
// Input:
//   text: original string.
//   pattern: pattern to remove.
//
// Output:
//   string: the final string after removing all occurrences.
//
// Time complexity: O(n + m) per removal? Actually O(n + m) overall because
//   each character is pushed/popped once using a stack.
//
// Constraints: pattern not empty.
//
// Notes:
//   Uses a stack of characters and the current KMP state. When a match is
//   complete, pop the matched characters from the stack and restore state.
string removeOccurrences(const string& text, const string& pattern) {
    int m = (int)pattern.size();
    if (m == 0) return text;
    vector<int> pi = buildPrefixFunction(pattern);
    string res;
    vector<int> stateStack;   // state after each char in res
    int j = 0;
    for (char c : text) {
        res.push_back(c);
        while (j > 0 && c != pattern[j]) j = pi[j - 1];
        if (c == pattern[j]) ++j;
        stateStack.push_back(j);
        if (j == m) {
            // remove last m chars
            for (int k = 0; k < m; ++k) {
                res.pop_back();
                stateStack.pop_back();
            }
            j = stateStack.empty() ? 0 : stateStack.back();
        }
    }
    return res;
}

// longestBorderBetween
// ---------------------
// What it does:
//   Given two strings a and b, finds the longest string that is a prefix of a
//   and also a suffix of b.
//
// Input:
//   a, b: strings.
//
// Output:
//   int: length of the longest common prefix/suffix.
//
// Time complexity: O(|a| + |b|).
//
// Constraints: delimiter '#' must not appear in a or b.
//
// Notes:
//   This is useful when you need to concatenate strings and reuse the border.
//   Example: a = "ab", b = "bc" → longest prefix of a that is suffix of b is
//   "b" (length 1).
int longestBorderBetween(const string& a, const string& b) {
    string combined = a + "#" + b;
    vector<int> pi = buildPrefixFunction(combined);
    return pi.back();
}

// kmpStateAtEachPosition
// -----------------------
// What it does:
//   For each position i in text, returns the KMP state (length of the longest
//   prefix of pattern that is a suffix of text[0..i]) after processing text[i].
//
// Input:
//   text, pattern: strings.
//
// Output:
//   vector<int> states of size n, where states[i] is the state after reading
//   text[i].
//
// Time complexity: O(n + m).
//
// Constraints: pattern not empty.
//
// Notes:
//   This is useful for DP or when you need the state at every step.
vector<int> kmpStateAtEachPosition(const string& text, const string& pattern) {
    int m = (int)pattern.size();
    vector<int> states;
    if (m == 0) return states;
    vector<int> pi = buildPrefixFunction(pattern);
    int j = 0;
    for (char c : text) {
        while (j > 0 && c != pattern[j]) j = pi[j - 1];
        if (c == pattern[j]) ++j;
        if (j == m) {
            j = pi[j - 1];
        }
        states.push_back(j);
    }
    return states;
}

// =======================================================================
// 8) Generic KMP for vectors (e.g., integers)
// =======================================================================

// buildPrefixFunction (generic)
// -----------------------------
// Same as string version but works for any vector<T>.
template<typename T>
vector<int> buildPrefixFunction(const vector<T>& p) {
    int m = (int)p.size();
    vector<int> pi(m, 0);
    for (int i = 1; i < m; ++i) {
        int j = pi[i - 1];
        while (j > 0 && p[i] != p[j]) j = pi[j - 1];
        if (p[i] == p[j]) ++j;
        pi[i] = j;
    }
    return pi;
}

// kmpSearch (generic)
// -------------------
template<typename T>
vector<int> kmpSearch(const vector<T>& text, const vector<T>& pattern) {
    vector<int> res;
    int n = (int)text.size(), m = (int)pattern.size();
    if (m == 0) return res;
    vector<int> pi = buildPrefixFunction(pattern);
    int j = 0;
    for (int i = 0; i < n; ++i) {
        while (j > 0 && text[i] != pattern[j]) j = pi[j - 1];
        if (text[i] == pattern[j]) ++j;
        if (j == m) {
            res.push_back(i - m + 1);
            j = pi[j - 1];
        }
    }
    return res;
}

// countOverlapping (generic)
template<typename T>
int countOverlapping(const vector<T>& text, const vector<T>& pattern) {
    return (int)kmpSearch(text, pattern).size();
}

// countNonOverlapping (generic)
template<typename T>
int countNonOverlapping(const vector<T>& text, const vector<T>& pattern) {
    vector<int> pos = kmpSearch(text, pattern);
    if (pos.empty()) return 0;
    int cnt = 1;
    int last = pos[0];
    int m = (int)pattern.size();
    for (int i = 1; i < (int)pos.size(); ++i) {
        if (pos[i] >= last + m) {
            ++cnt;
            last = pos[i];
        }
    }
    return cnt;
}

// =======================================================================
// 9) Example usage (optional)
// =======================================================================

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

    // Example 1: search
    string text = "ababcababcabc", pat = "abc";
    vector<int> pos = kmpSearch(text, pat);
    cout << "Occurrences at: ";
    for (int p : pos) cout << p << " ";
    cout << "\n";  // 2, 7, 10

    // Example 2: count overlapping
    cout << "Overlapping count: " << countOverlapping("aaaa", "aa") << "\n";  // 3

    // Example 3: non-overlapping
    cout << "Non-overlapping count: " << countNonOverlapping("aaaa", "aa") << "\n";  // 2

    // Example 4: period
    cout << "Smallest period of 'ababab': " << smallestPeriod("ababab") << "\n";  // 2

    // Example 5: automaton DP
    ll mod = 1000000007LL;
    cout << "Binary strings of length 3 avoiding '11': "
         << countStringsAvoidPattern(3, "11", 2, mod) << "\n";  // 5 (000,001,010,100,101)

    // Example 6: prefix occurrences
    vector<int> occ = prefixOccurrences("aaaa", "aa");
    cout << "Prefix 'a' occurs " << occ[1] << " times, prefix 'aa' occurs " << occ[2] << " times\n";

    // Example 7: remove occurrences
    cout << "Remove 'ab' from 'aabab': " << removeOccurrences("aabab", "ab") << "\n";  // "a"

    return 0;
}