#include <iostream>

using namespace std;
typedef long long ll;
const int alphabet_size = 26;
const ll MOD = 1e9 + 7;
void rolling_hash(string s, int window_size, string pattern) {
    ll res_hash = 0;
    for(int i = 0; i < (int) pattern.size(); i++) {
        res_hash = (res_hash * alphabet_size + pattern[i]) % MOD;
    }
    int n = (int) s.size();
    vector<ll> powers(n + 1, 1);
    for(int i = 1; i <= n; i++) {
        powers[i] = (powers[i - 1] * alphabet_size) % MOD;
    }
    ll hash = 0;
    for(int i = 0; i < window_size; i++) {
        hash = (hash * alphabet_size + s[i]) % MOD;
    }
    if(hash == res_hash) {
        bool ok = true;
        for(int i = 0; i < window_size; i++) {
            if(pattern[i] != s[i]) {
                ok = false;
                break;
            }
        }
        if(ok) {
            cout << 0 << endl;
        }
    }
    vector<ll> res(n - window_size + 1);
    res[0] = hash;
    for(int i = 1; i <= n - window_size; i++) {
        hash = (hash - powers[window_size - 1] * s[i - 1]);
        while (hash < 0) {
            hash += MOD;
        }
        hash %= MOD;
        hash = (hash * alphabet_size + s[i + window_size - 1]) % MOD;
        if(hash == res_hash) {
            bool ok =true;
            for(int j = 0; j < window_size; j++) {
                if(pattern[j] != s[i + j]) {
                    ok = false;
                    break;
                }
            }
            if(ok) {
                cout << i << endl;
            }
        }
        res[i] = hash;
    }

}
int main() {
    ios_base::sync_with_stdio(false);
    string text = "AABAACBAA";
    string pattern = "BAA";
    rolling_hash(text, 3, pattern);
   return 0;
}