#include "peru.h"
#include<bits/stdc++.h>
#define int long long
using namespace std;
int INF = numeric_limits<int>::max()/2;
int mod = 1e9+7;
struct SegmentTree{
int len = 1;
vector<int> S;
SegmentTree(vector<int> arr){
int n = arr.size();
while(len < n){
len <<= 1;
}
S.resize(2*len);
for(int i = 0; i < n; i++){
S[i+len] = arr[i];
}
for(int i = len-1; i > 0; i--){
S[i] = max(S[i*2], S[i*2+1]);
}
}
int query(int ql, int qr, int l = 0, int r = -2, int i = 1){
if(r == -2) r = len;
if(ql <= l && r <= qr) return S[i];
if(r <= ql || qr <= l) return 0;
int mid = (l+r)/2;
return max(query(ql,qr,l,mid,i*2),query(ql,qr,mid,r,i*2+1));
}
};
int exp(int a, int k){
if(k == 0) return 1;
int res = exp(a,k/2);
if(k % 2 == 0) return (res * res) % mod;
return ((res*res% mod) * a )% mod;
}
int32_t solve(int32_t n, int32_t k, int32_t* S){
vector<int> v(n);
for(int i = 0; i < n; i++){
v[i] = S[i];
}
vector<int> dp(n+1, INF);
dp[0] = 0;
int res = 0;
SegmentTree seg(v);
for(int i = 1; i <= n; i++){
int ma = 0;
// for(int p = i; p >= max(1LL, i-k+1LL); p--){
// ma = max(ma, v[p-1]);
// dp[i] = min(dp[i], dp[p-1]+ma);
// }
dp[i] = dp[max(0LL, i-k)];
int l = max(0LL, i-k);
ma = seg.query(l, i);
dp[i] += ma;
res += ((dp[i]%mod) * exp(23, n-i))%mod;
res %= mod;
}
return res;
}
