#include "peru.h"
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define tiii tuple<int,int,int>
using namespace std;
int INF = numeric_limits<int>::max()/2;
int mod = 1e9+7;
int MAXK = 4;
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);
vector<vector<int>> dpJ(MAXK, vector<int>(n+1, INF));
vector<vector<tiii>> dpJP(MAXK, vector<tiii>(n+1, {INF,INF,INF}));
SegmentTree seg(v);
dpJ[0][0] = 0;
dpJP[0][0] = {0,0,0};
for(int i = 1; i <= n; i++){
dpJ[0][i] = dpJ[0][i-1]+v[i-1];
dpJP[0][i] = make_tuple(dpJ[0][i-1], v[i-1], i-1LL);
}
for(int k = 1; k < MAXK; k++){
dpJ[k][0] = 0;
dpJP[k][0] = {0,0,0};
int p2 = 1 << k;
for(int i = 1; i <= n; i++){
int v1, m1, l1;
tie(v1,m1,l1) = dpJP[k-1][i];
int v2, m2, l2;
int prev =max(0LL,i-p2);
tie(v2,m2,l2) = dpJP[k][prev];
// either staying at the same point
int r1 = m1+dpJ[k][l1];
// or moving as far as possible
int r2 = dpJ[k][prev]+seg.query(max(0LL,i-p2), i);
if(r1 < r2){
dpJ[k][i] = r1;
dpJP[k][i] = {dpJ[k][l1],m1,l1};
}else{
dpJ[k][i] = r2;
dpJP[k][i] = {v2,seg.query(max(0LL,i-p2), i),prev};
}
}
}
dp[0] = 0;
int res = 0;
for(int i = 1; i <= n; i++){
tiii r = {INF,INF,INF};
int v = INF;
int csum = 0;
for(int k = 0; k < MAXK; k++){
int p2 = 1 << k;
if((K & p2) == 0) continue;
csum += p2;
if(get<0>(r) == INF) {
r = dpJP[k][i];
v = dpJ[k][i];
continue;
}
int v1, m1, l1;
tie(v1,m1,l1) = r;
int v2, m2, l2;
int prev =max(0LL,i-csum);
tie(v2,m2,l2) = dpJP[k][prev];
// either staying at the same point
int r1 = m1+dp[l1];
// or moving as far as possible
int r2 = dp[prev]+seg.query(max(0LL,prev), i);
if(r1 < r2){
v = r1;
r = {dpJ[k][l1],m1,l1};
}else{
v = r2;
r = { dp[prev],seg.query(max(0LL,prev), i),prev};
}
}
dp[i] = v;
res += ((dp[i]%mod) * exp(23, n-i))%mod;
res %= mod;
}
return res;
}
