int allWays = pwr(m, n);
int ans = 0;
for(int i=1;i<n;i++) {
    if(isPrime[i] && n % i == 0 && i <= m) {
        int iLengthPeriod = nPr(factorialArray, m, i);
        allWays = (1ll * allWays - iLengthPeriod + mod) % mod;
        ans = (1ll * ans + (1ll * iLengthPeriod * inverse(i)) % mod) % mod;
    }
}

ans = (1ll * ans + (1ll * allWays * inv(n)) % mod) % mod;
cout << ans << "\n";

int recurse(int in, int maximumMatchingPrefixLength, int n, int m, int numberOfRequiredSubString) {
    if(in == n) {
        return numberOfRequiredSubString > 0;
    }

    int ans = 0;

    // matching case
    if(maximumMatchingPrefixLength+1 >= m) {
        // insert the last character, and now maximum matching prefix would become 0
        // and number of required substring would increase by 1
        ans += recurse(in+1, 0, n, m, numberOfRequiredSubString+1);
    }
    else {
        // insert that character, which is matching to next character after maximum matching prefix
        // for ex, required substring = ABC
        // and current string is XGAB
        // then, we are inserting C here
        ans += recurse(in+1, maximumMatchingPrefixLength+1, n, m, numberOfRequiredSubString);
    }

    // non matching case
    // insert all those characters, which are coming after any prefix length of Required string
    // and recurse for next position, with that prefix length
    set<char> uc;
    uc.insert(s[maximumMatchingPrefixLength]);
    maximumMatchingPrefixLength = lps[maximumMatchingPrefixLength - 1];
    while(maximumMatchingPrefixLength > 0) {
        uc.insert(s[maximumMatchingPrefixLength]);
        ans += recurse(in+1, lps[maximumMatchingPrefixLength-1], n, m, numberOfRequiredSubString);
        maximumMatchingPrefixLength = lps[maximumMatchingPrefixLength-1];
    }    
    
    // insert other characters, which did not come till now
    ans += (26 - uc.size()) * recurse(in+1, 0, n, m, numberOfRequiredSubString);

    return ans;

}

ll solve(int i, int n, int j, string &s)
{
    if(done[i][j]) return dp[i][j];
    done[i][j] = true;
    if(i == n) return dp[i][j] = (j==(int)s.size()?1:0);
    if(j == (int)s.size())
    {
        return dp[i][j] = (mxK*solve(i+1,n,j,s))%mod;
    }
    ll ans = 0;
    int t;
    for(int k = 0; k < mxK; k++)
    {
        t = j;
        while(true)
        {
            if(k == s[t]-'A')
            {
                t++;
                break;
            }
            else if(t)
            {
                t = kmp[t-1];
            }
            else break;
        }
        ans += solve(i+1,n,t,s);
        ans %= mod;
    }
    return dp[i][j] = ans;
}

int l=0, r;
for(r=0;r<n;r++) {

    if(!up.empty() && *up.begin() <= a[r]) {
        up.insert(a[r]);
    }
    else {
        low.insert(a[r]);
    }
    
    if(up.size() > low.size()) {
        low.insert(*up.begin());
        up.erase(up.begin());
    }

    if(up.size()+1 < low.size()) {
        up.insert(*low.rbegin());
        multiset<int>::iterator itr = low.end();
        itr--;
        low.erase(itr);
    }
    
    if(r >= k-1) {
        
        cout << *low.rbegin() << " ";
        if(!low.empty() && low.count(a[l])) {
            low.erase(low.find(a[l]));
        }
        else if(!up.empty() && up.count(a[l])) {
            up.erase(up.find(a[l]));
        }
        l++;
    }
}
cout << "\n";

void ins(long val) {         // insert val into sets
    long a = *low.rbegin();  // current median
    if (a < val) {
        up.insert(val);
        if (up.size() > M / 2) {
            low.insert(*up.begin());
            up.erase(up.find(*up.begin()));
        }
    } else {
        low.insert(val);
        if (low.size() > (M + 1) / 2) {
            up.insert(*low.rbegin());
            low.erase(low.find(*low.rbegin()));
        }
    }
}

void er(long val) {  // erase from sets
    if (up.find(val) != up.end()) up.erase(up.find(val));
    else low.erase(low.find(val));
    if (low.empty()) {
        low.insert(*up.begin());
        up.erase(up.find(*up.begin()));
    }
}
low.insert(arr[0]);
for (int i = 1; i < M; i++) ins(arr[i]);
cout << *low.rbegin() << " ";
for (long i = M; i < N; i++) {
    if (M == 1) {
        ins(arr[i]);
        er(arr[i - M]);
    } else {
        er(arr[i - M]);
        ins(arr[i]);
    }
    cout << *low.rbegin() << " ";
}