Submission

Score: 150

User: qweqwe

Problemset: Chocolate

Language: cpp

Time: 1.085 second

Submitted On: 2026-10-08 20:11:37

/*
						 :::=
                        .:.:.
                        :.-
                  .:-:..:=-=.:--:.
                -:.................:-.
             =.........................-
          :::........................:..:
      .-::=...    ............:.......:==-=::
   ==-:::=.    ....:......:....:........=+-:::=
	    :    .::...-.....::..............==:.....
       ..  ...=...-:..:..::..............=+:....=
       : ....::..- ::.:..: .:.....:.....-.--....:.
       -::...=:::.  =.:..-   =.....=.....:-=:...:.
      .::....=####+.:-:..-    :=-::::....:==:...:
      .:::..:=. =++*:.::.:. : .=+-===....:-=:...-
       -:+..-= .===:-  =:.- -=++===*=...:+==::..=
       ::+..--  :..:.   :-: :===:= *-...+-.-::..=
    	===.:=             - ...-   :..-=  -::..:.
         :::.:-                    -..:-   -::...:
            ::  ::                 :.-     =::...-
             :      :-:.     ..:: =.=     --::....:
                    .-==*+==--   ::       =::.....-
                   -:+==:=== :-.          ---......:
                  ###==+.===+ :+.        =:-=:...:.:
                =***#=+:.====#**#:       --:=:...-.::
               #***+===..====+**##-     -:.-:...:+:.-
             .==##=====-+======#= *+    =  =:...: =:-
             : -=.-====:-====-=##=:#+  :  :-:..=   .==
                 =######*#==##*#*-= =     -:.::
                 -=#.  #  #*###*--.-:    =:::
                   .===+=-+===+.        :=.
                    :    :-  =:.
                    :====:-..=#.
                     #***::*###
                     *###..#**#
                     --=. .***-
*/
#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 = 5001, MXK = 5001, MXC = 6;
const int MOD = 1e9+7;
const int INF = 2*1e9;
int dp[2][4*MXN],lazy[2][4*MXN];
__int128 pfq[MXC][MXN];
int poww[MXN],arr[MXN];
int ncr[MXC][MXC];

void apply(int node,int col,int l,int r,int x){
	dp[col][node] = (dp[col][node]+1LL*x*(r-l+1))%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>qr||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;
}

__int128 ipow(ll x,int p){
	__int128 res=1;
	while (p--){
		res*=x;
	}return res;
}

__int128 get(int j,int x,int c){
	__int128 ans=0;
	for (int q=0;q<=c;q++){
		ans+=(__int128)ncr[c][q] * (ipow(-j,c-q)) * (pfq[q][x]-pfq[q][j]);
	}return ans;
}

void pre(){
	for (int i=0;i<=5;i++){
		ncr[i][0]=1;
	}
	for (int i=0;i<=5;i++){
		for (int j=1;j<=i;j++){
			ncr[i][j]=ncr[i-1][j]+ncr[i-1][j-1];
		}
	}
}

int bs(int j,int n,ll a,int c){
	int l=j+1,r=n;
	int ans=j;
	while (l<=r){
		int mid = (l+r)/2;
		if (get(j,mid,c)<=a){
			l=mid+1;ans=mid;
		}else r=mid-1;
	}return ans;
}

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;
	pre();
	for (int q=0;q<=c;q++){
		__int128 sum=0;
		for (int i=1;i<=n;i++){
			sum+=ipow(i-1,q)*arr[i-1];
			pfq[q][i]=sum;
		}
	}
	
	/*
	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 = bs(j,n,a-1,c)+1;
			int r = bs(j,n,b,c);
			if (l>r) continue;
			//cout << *(pf[j+1]+j+1) << " " << *(pf[j+1]+n+1) << "\n";
			ll val=query(1,0,n,j,j,0);
			if (!val) continue;
			//cout << pf[j+1][l] << " " << pf[j+1][r] << " " << val << "\n";
			upd(1,0,n,l,r,val,1);
		}
		memcpy(dp[0], dp[1], sizeof(dp[0]));
		memcpy(lazy[0], lazy[1], sizeof(lazy[0]));
		memset(dp[1], 0, sizeof(dp[1]));
		memset(lazy[1], 0, sizeof(lazy[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,0);
	return 0;
}