Expert.
Put your skills to the test.

Problem summary

Generate A1=FIRST and Ai=(Ai−1·MUL+ADD) mod MOD. On day i choose the maximum among the most recent min(i,K) values. Sum these daily maxima.

Constraints

1 ≤ K ≤ N ≤ 10000000; 0 ≤ FIRST,MUL,ADD < MOD ≤ 1000000007.

Worked example

Official sample; other valid outputs may exist.

7 3
5 3 2 23

79

Solution analysis

1. Keep a deque of candidate indices and values in decreasing value order. Remove expired candidates from the front. When a new value arrives, remove every smaller or equal value from the back: the newer value is at least as good and expires later.
2. The front is now the current window maximum. Add it to a 64-bit answer, generate the next value with a 64-bit product, and continue without storing the whole sequence.
3. The sample generates 5,17,7,0,2,8,3. Its daily maxima are 5,17,17,17,7,8,8, whose sum is 79.

Why it works

A discarded back candidate is dominated by the newer candidate in every future window that could contain it. Front expiration removes precisely those candidates outside the window. Therefore every remaining possible maximum is represented and the decreasing deque’s front is the maximum. Every daily addition is correct, hence so is their sum.

Watch out. The window contains K values, including today. The largest sum is about 10^16 and the generator product needs 64 bits.

An independently written complete program with standard headers.

// Key idea: A discarded back candidate is dominated by the newer candidate in every future window that
// could contain it. Front expiration removes precisely those candidates outside the window.
#include<iostream>
#include<deque>
#include<utility>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k;
    long long value,mul,add,mod;
    cin>>n>>k>>value>>mul>>add>>mod;
    deque<pair<int,int>>candidates;
    long long answer=0;
    for(int i=0;i<n;++i){
        while(!candidates.empty()&&candidates.front().first<=i-k){
            candidates.pop_front();
        }
        while(!candidates.empty()&&candidates.back().second<=value){
            candidates.pop_back();
        }
        candidates.push_back({i,static_cast<int>(value)});
        answer+=candidates.front().second;
        value=(value*mul+add)%mod;
    }
    cout<<answer<<'\n';
}