#include <bits/stdc++.h> 
#include "peru.h"
 
using namespace std; 
 
typedef long long ll;
 
const int N = 25 * 1e3 + 10;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
 
ll dp[N];
 
int add(int a, int b){
	if(a + b < 0) return a + b + N;
	if(a + b >= N) return a + b - N;
	return a + b;
}
 
ll MODadd(ll a, ll b){
	return (a + b) % MOD;
}
 
ll MODmult(ll a, ll b){
	return a * b % MOD;
}
 
struct elem{
	ll val, maxi;
	int ind;
	elem(){
		val = 0;
		maxi = 0;
		ind = 0;
	};
};
 
struct monostack{
	elem arr[N];
	int ind = 0;
	void push(elem x){
		if(ind) x.val = min(x.val, arr[ind - 1].val);
		arr[ind] = x;
		ind++;
	};
	elem pop(){
		if(ind){
			ind--;
			return arr[ind];
		}
		assert(false);
		return arr[ind];
	};
	elem front(){
		if(ind) return arr[ind - 1];
		assert(false);
		return arr[ind];
	};
	ll mini(){
		if(ind) return arr[ind - 1].val;
		return INF;
	}
	int size(){
		return ind;
	};
	void clear(){
		ind = 0;
	};
};
 
struct monodeck{
	monostack l, r;
	elem arr[N];
	int L = 0, R = 1;
	void build(){
		if(l.size() > 0 && r.size() > 0) return;
		//printf("building\n");
		int mi = (L + R) >> 1;
		if(L > R) mi = (L - N + R) >> 1;
		l.clear();
		r.clear();
		for(int i = mi; i != L; i = add(i, -1)){
			assert(i >= 0);
			l.push(arr[i]);
		} 
		for(int i = mi + 1; i != R; i = add(i, 1)){
			assert(i < N);
			r.push(arr[i]);
		} 
	}
	void push_front(elem x){
		arr[L] = x;
		l.push(x);
		L = add(L, -1);
		build();
	};
	void push_back(elem x){
		arr[R] = x;
		r.push(x);
		R = add(R, 1);
		build();
	};
	elem pop_front(){
		if(l.size() == 0) swap(l, r);
		L = add(L, 1);
		elem ret = l.pop();
		build();
		return ret;
	};
	elem pop_back(){
		if(r.size() == 0) swap(l, r);
		R = add(R, -1);
		elem ret = r.pop();
		build();
		return ret;
	};
	elem front(){
		return arr[add(L, 1)];
	};
	elem back(){
		return arr[add(R, -1)];
	};
	ll mini(){
		return min(l.mini(), r.mini());
	}
	int size(){
		return l.size() + r.size();
	};
};
 
ll DP(int x){
	if(x < 0) return 0;
	return dp[x];
}
 
int solve(int n, int k, int* arr){
	elem res, p; 
	monodeck s;
	dp[0] = arr[0];
	p.val = arr[0];
	p.maxi = arr[0];
	p.ind = 0;
	s.push_back(p);
	for(int i = 1; i < n; i++){
		if(i >= k){
			res = s.pop_front();
			//printf("ind = %d\n", res.ind);
			p.val = dp[i - k] + res.maxi;
			p.maxi = res.maxi;
			p.ind = i - k + 1;
			if(p.ind != i){
				if(s.size()){ 
					if(s.front().ind != p.ind) s.push_front(p);
				} else { 
					s.push_front(p);
				}
				//if(i == 2) printf("i = 2 ! %d\n", s.size());
			} 
		}
		bool del = false;
		while(s.size() && s.back().maxi <= arr[i]){
			res = s.pop_back();
			del = true;
		}
		//if(i == 3) printf("siz = %d maxi %lld front %d\n", s.size(), s.mini(), s.L);
		if(del){
			p.val = DP(res.ind - 1) + arr[i];
			p.maxi = arr[i];
			p.ind = res.ind;
			s.push_back(p);
			//printf("%d - diff %d\n", i, res.ind);
		} else {
			p.val = arr[i] + dp[i - 1];
			p.maxi = arr[i];
			p.ind = i;
			s.push_back(p);
			//printf("%d - same\n", i);
		}
		dp[i] = s.mini();
	}
	ll ans = 0;
	ll c = 1;
	for(int i = n - 1; i >= 0; i--){
		ans = MODadd(ans, MODmult(dp[i], c));
		c = MODmult(c, 23);
		//printf("%lld ", dp[i]);
	}
	//printf("\n");
	return ans;
}