Submission

Score: 150

User: C12

Problemset: Chocolate

Language: cpp

Time: 1.093 second

Submitted On: 2026-03-16 21:04:28

#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9+7;
#define ll long long
#define pii pair<ll,int>

const ll mx_h = 2e9+1;

ll calibrate(ll a){
    while(a < 0) a += mod;
    while(a >= mod) a -= mod;
    return a;
}

ll pow_ll(ll a,ll p){
    ll res = 1;
    while(p){
        if(p & 1) res = (res * a);
        if(a < mx_h) a = (a * a);
        p >>= 1;
        if(res > mx_h) return mx_h;
    }
    return res;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    ll n,m,c;

    cin >> n >> m >> c;

    vector<ll> vec(n);

    vector<ll> prev (n,0);
    vector<ll> cur (n,0);

    for(int i = 0;i < n;i++) cin >> vec[i];

    vector<ll>pre(n,0);
    vector<ll>mul(n+1);

    for(int i = 0;i <= n;i++){
        mul[i] = pow_ll(i,c);
        // cout << mul[i] << ' ';
    }
    // cout << '\n';

    // return 0;

    // for(int i = 0;i < n;i++){
    //     pre[i][i] = vec[i] * mul[0];
    //     for(int j = i-1;j >= 0;j--){
    //         if(mul[i-j] == mx_h || pre[i-1][j] > mx_h)
    //             pre[i][j] = mx_h;
    //         else
    //             pre[i][j] = pre[i-1][j] + (vec[i] * mul[i-j]);
    //     }
    // }
    
    // for(int i = 0;i < n;i++){
    //     for(int j = 0;j < n;j++){
    //         cout << pre[i][j] << '\t';
    //     }
    //     cout << '\n';
    // }

    ll lo;
    ll hi;

    cin >> lo >> hi;


    pre[0] = vec[0] * mul[0];
    for(int j = 1;j < n;j++){    
        pre[j] = pre[j-1] + (vec[j] * mul[j]);
    }

    // for(int j = 0;j < n;j++){
    //     cout << pre[j] << ' ';
    // }
    // cout << '\n';

    int i = 0;
    while(i < n && pre[i] < lo){
        i++; 
    }

    while(i < n && pre[i] <= hi){
        prev[i] = 1;
        // cout << i << '\n';
        i++;
    }

    pre = vector<ll>(n,0);
    pre[0] = vec[0] * mul[0];

    for(int k = 1;k < m;k++){
        for(int i = 1;i < n;i++){
            for(int j = 0;j <= i;j++){    
                pre[j] = pre[j] + (vec[i] * mul[i-j]);
            }
     
            
            for(int j = 1;j <= i;j++){
                if(pre[j] >= lo && pre[j] <= hi){
                    cur[i] += prev[j-1];
                    cur[i] = calibrate(cur[i]);
                }
            }

            // cout << i << '\t';
            // for(int j = 0;j < n;j++){
            //     cout << pre[j] << ' ';
            //     // cout << cur[j] << ' ';
            // }
            // cout << '\n';

            // cout << i << '\t';
            // for(int j = 0;j < n;j++){
            //     // cout << pre[j] << ' ';
            //     cout << cur[j] << ' ';
            // }
            // cout << '\n';

        }
        pre = vector<ll> (n,0);
        pre[0] = vec[0] * mul[0];

        prev = cur;
        cur = vector<ll> (n,0);
    }

    // for(int k = 0;k < m;k++){
    //     for(int i = 0;i < n;i++){
    //         cout << dp[k][i] << '\t';
    //     }
    //     cout << '\n';
    // }
    
    cout << prev[n-1];

    return 0;
}