fn main() {
    let mut arr: Vec<isize> = vec![2, 5, 5, 7, 7];
    let limit: isize = 20;
    let ans = max_investment(&mut arr, limit);
    println!("ans = {}", ans);
}

fn max_investment(arr: &mut Vec<isize>, mut limit: isize) -> isize {
    const MOD: isize = 1000000007;
    arr.sort();
    let n = arr.len() as isize;
    let mut ans: isize = 0;
    let mut r = n - 1;
    let mut l = r;
    while limit > 0 && r != -1 {
        while l >= 0 && arr[l as usize] == arr[r as usize] {
            l -= 1;
        }
        let big = arr[r as usize];
        let small = if l == -1 { 0 } else { arr[l as usize] };
        let teams = n - l - 1;
        let all = (big - small) * teams;
        if limit >= all {
            ans += get(big, small + 1, teams);
            ans %= MOD;
            limit -= all;
        } else {
            let a = limit / teams;
            ans += get(big, big - a + 1, teams) + (big - a) * (limit % teams);
            ans %= MOD;
            limit = 0;
        }
        r = l;
    }
    return ans % MOD;
}

fn get(up: isize, down: isize, num: isize) -> isize {
    return num * ((up + down) * (up - down + 1) / 2);
}