Divide Cake into Five

Segtree is a quintuplet tutor. Today is Christmas Eve, so I'm trying to divide the round cake into five equal parts for the quintuplets.

The cake is divided into $ N $ pieces from the center in a fan shape, $ i $ th and $ i + 1 $ th ($ 1 \ leq i \ leq N -1 $), $ N $ th and $ 1 $ The second piece is next to each other.

The size of the $ i $ th piece is $ A_i $. If the sum of the sizes of all the pieces is $ S $, then $ S $ is guaranteed to be a multiple of $ 5 $ for all inputs.

Given a non-negative integer $ Y $. How to divide a cake into quintuplets that meet the following conditions is called "cake quintet".

* Everyone takes one or more pieces.
* The pieces each take in the cake are connected. In other words, when the pieces are grouped by the taker, there is no set of pieces in the same group that cannot be reached repeatedly by moving to the same group and adjacent pieces.
* There is no piece that no one takes.
* For everyone, if the size of the piece to be taken is $ X $, it always satisfies $ X + Y \ geq S / 5 $.



Find out how many different ways to divide the cake so that it becomes "five equal parts of the cake".

input

Input is given from standard input in the following format.


$ N $ $ Y $
$ A_1 $ $ A_2 $ $ \ ldots $ $ A_N $


output

Please output the number according to how to divide the cake so that it becomes "five equal parts of the cake".

However, insert a line break at the end.

Constraint

* $ 5 \ leq N \ leq 300 $
* $ 1 \ leq A_i \ leq 10 ^ 9 $
* $ 0 \ leq Y \ leq 10 ^ 9 $
* All inputs are integers.



Input example 1


5 0
1 1 1 1 1


Output example 1


1


Input example 2


10 27
3 1 4 1 5 9 2 6 5 4


Output example 2


252






Example

Input

5 0
1 1 1 1 1


Output

1
#include <bits/stdc++.h>
using namespace std;

int main(){
    int N, Y;
    cin >> N >> Y;
    vector<int64_t> A(2*N), S(2*N+1);
    for(int i=0; i<N; i++){
        cin >> A[i];
        A[i+N] = A[i];
    }
    for(int i=0; i<2*N; i++){
        S[i+1] = S[i] + A[i];
    }
    int64_t L = accumulate(A.begin(), A.end(), 0LL) / 10 - Y;
    int64_t ans = 0;
    for(int s=N; s>=0; s--){
        int t = s+N;
        int64_t dp[601][6] = {0};
        dp[s][0] = 1;
        for(int i=s; i<t; i++) for(int j=i+1; j<=t; j++) if(S[j] - S[i] >= L) for(int k=0; k<5; k++){
            if(k == 0 && j <= N) continue;
            dp[j][k+1] += dp[i][k];
        }
        ans += dp[t][5];
    }
    cout << ans << endl;
    return 0;
}

