Submission

Score: 70

User: qweqwe

Problemset: Chocolate

Language: cpp

Time: 0.015 second

Submitted On: 2026-10-08 18:58:10

/*
						 :::=
                        .:.:.
                        :.-
                  .:-:..:=-=.:--:.
                -:.................:-.
             =.........................-
          :::........................:..:
      .-::=...    ............:.......:==-=::
   ==-:::=.    ....:......:....:........=+-:::=
	    :    .::...-.....::..............==:.....
       ..  ...=...-:..:..::..............=+:....=
       : ....::..- ::.:..: .:.....:.....-.--....:.
       -::...=:::.  =.:..-   =.....=.....:-=:...:.
      .::....=####+.:-:..-    :=-::::....:==:...:
      .:::..:=. =++*:.::.:. : .=+-===....:-=:...-
       -:+..-= .===:-  =:.- -=++===*=...:+==::..=
       ::+..--  :..:.   :-: :===:= *-...+-.-::..=
    	===.:=             - ...-   :..-=  -::..:.
         :::.:-                    -..:-   -::...:
            ::  ::                 :.-     =::...-
             :      :-:.     ..:: =.=     --::....:
                    .-==*+==--   ::       =::.....-
                   -:+==:=== :-.          ---......:
                  ###==+.===+ :+.        =:-=:...:.:
                =***#=+:.====#**#:       --:=:...-.::
               #***+===..====+**##-     -:.-:...:+:.-
             .==##=====-+======#= *+    =  =:...: =:-
             : -=.-====:-====-=##=:#+  :  :-:..=   .==
                 =######*#==##*#*-= =     -:.::
                 -=#.  #  #*###*--.-:    =:::
                   .===+=-+===+.        :=.
                    :    :-  =:.
                    :====:-..=#.
                     #***::*###
                     *###..#**#
                     --=. .***-
*/
#include <bits/stdc++.h>
#define akneru cin.tie(0)->sync_with_stdio(0)
using namespace std;
using ll = long long;
using pii = pair<ll,ll>;
using vi = vector<ll>;
using vvi = vector<vector<ll>>;
using db = long double;

const int MXN = 2001, MXK = 21;
const int MOD = 1e9+7;
int dp[MXK][4*MXN],lazy[MXK][4*MXN],pf[MXN][MXN];
int poww[MXN],arr[MXN];

void apply(int node,int col,int l,int r,int x){
	dp[col][node] += x*(r-l+1);
	dp[col][node] %= MOD;
	lazy[col][node] += x;
	lazy[col][node] %= MOD;
}

void flush(int node,int col,int l,int r){
	if (!lazy[col][node]||l==r) return;
	int mid = (l+r)/2;
	apply(2*node,col,l,mid,lazy[col][node]);
	apply(2*node+1,col,mid+1,r,lazy[col][node]);
	lazy[col][node]=0;
}

int merge(int a,int b){
	return (a%MOD+b%MOD)%MOD;
}

void upd(int node,int l,int r,int ql,int qr,ll val,int col){
	if (ql>r||qr<l) return;
	if (ql<=l&&qr>=r){
		apply(node,col,l,r,val);
		return;
	}
	flush(node,col,l,r);
	int mid = (l+r)/2;
	upd(2*node,l,mid,ql,qr,val,col);
	upd(2*node+1,mid+1,r,ql,qr,val,col);
	dp[col][node]=merge(dp[col][2*node],dp[col][2*node+1]);
}

int query(int node,int l,int r,int ql,int qr,int col){
	if (ql>r||qr<l) return 0;
	if (ql<=l&&qr>=r){
		return dp[col][node];
	}
	flush(node,col,l,r);
	int mid = (l+r)/2;
	int sum=query(2*node,l,mid,ql,qr,col)%MOD+query(2*node+1,mid+1,r,ql,qr,col)%MOD;
	return sum%MOD;
}

int main(){
	akneru;
	int n,k,c;cin >> n >> k >> c;
	for (int i=0;i<n;i++) cin >> arr[i];
	ll a,b;cin >> a >> b;
	if (c==0){
		for (int i=0;i<n;i++){
			poww[i]=1;
		}
	}else{
		poww[0]=0;
		for (int i=1;i<=n;i++){
			ll curr=1,cur=i;
			for (int j=0;j<c;j++){
				curr*=cur;
				if (curr>=1e10){
					curr=-1;break;
				}
			}
			poww[i]=curr;
		}
	}
	for (int i=1;i<=n;i++){
		ll sum=0;int j=i,cur=0;
		while (j<=n){
			sum+=poww[cur]*arr[j-1];
			if (sum>=2*1e9+1) break;
			pf[i][j]=sum;cur++;j++;
		}
	}
	/*
	for (int i=0;i<=n;i++){
		cout << poww[i] << " ";
	}cout << "\n";
	for (int i=0;i<=n;i++){
		for (int j=0;j<=n;j++){
			cout << pf[i][j] << " ";
		}cout << "\n";
	}
	*/
	upd(1,0,n,0,0,1,0);
	for (int i=0;i<k;i++){
		for (int j=0;j<n;j++){
			int l = lower_bound(pf[j+1]+j+1,pf[j+1]+n+1,a)-pf[j+1];
			int r = upper_bound(pf[j+1]+j+1,pf[j+1]+n+1,b)-pf[j+1]-1;
			
			//cout << *(pf[j+1]+j+1) << " " << *(pf[j+1]+n+1) << "\n";
			
			ll val=query(1,0,n,j,j,i);
			//cout << pf[j+1][l] << " " << pf[j+1][r] << " " << val << "\n";
			upd(1,0,n,l,r,val,i+1);
		}
	}
	/*
	for (int i=0;i<=k;i++){
		for (int j=0;j<=n;j++){
			cout << query(1,0,n,j,j,i) << " ";
		}cout << "\n";
	}
	*/
	cout << query(1,0,n,n,n,k);
	return 0;
}