Problem Description

There are $ N $ participants in the QUPC 2022 onsite event at Kyushu University. The AtCoder rating of the $ i $-th participant is $ A_i $.

We want to divide the $ N $ participants into several teams such that the following conditions are satisfied:

• Each team has between $ 1 $ and $ 3 $ members.
• The average AtCoder rating of the participants in each team is at most $ K $.
• Regardless of the AtCoder rating value, it is possible for a participant to form a team of one.

Determine the number of ways to form teams that satisfy these conditions. It is guaranteed that the answer does not exceed $ 10^{18} $ under the given constraints.

Input Format

The input is given from the standard input in the following format:

$ N $ $ K $ $ A_1 $ $ A_2 $ $ ... $ $ A_N $

Output Format

Output the number of ways to form teams that satisfy the conditions.

Sample Input and Output

Sample Input #1

3 2000
1999 2000 2001

Sample Output #1

4

Sample Input #2

4 2000
2500 3000 1000 2000

Sample Output #2

6

Sample Input #3

12 2000
3092 2432 2312 1867 1794 1730 1670 1523 1495 1299 1169 1024

Sample Output #3

297042

Notes/Hints

Constraints

• $1 \leq N \leq 18$
• $0 \leq K \leq 4208$
• $0 \leq A_i \leq 4208$
• All inputs are integers

Sample Explanation 1

There are $ 5 $ ways to form teams of up to $ 3 $ people, and the top $ 4 $ ways satisfy the conditions:
- Team with the 1st participant alone, team with the 2nd participant alone, team with the 3rd participant alone
- Team with the 1st, 2nd, and 3rd participants
- Team with the 1st and 2nd participants, team with the 3rd participant alone
- Team with the 1st and 3rd participants, team with the 2nd participant alone
- Team with the 2nd and 3rd participants, team with the 1st participant alone

见题面 Input 部分

见题面 Output 部分