Chọn số

Bạn Dũng viết lên bảng \(N\) số nguyên dương \(a_1, a_2, \ldots, a_N\) khác nhau đôi một. Biết rằng, dãy con tăng độ dài \(L\) là dãy được định nghĩa:

• \(1 \le k_1 < k_2 < \ldots < k_L \le N\); \(L \ge 2\);

• \(a_{k_1} < a_{k_2} < \ldots < a_{k_L}\).

Hai dãy con tăng của dãy ban đầu được gọi là khác nhau nếu có ít nhất một phần tử khác nhau.

Bạn Dũng có một số nguyên dương \(X\), bạn ấy sẽ thực hiện các nhiệm vụ khác nhau:

• Nếu \(X \le N\) thì bạn Dũng sẽ đếm số lượng cách chọn \(X\) số chẵn từ dãy trên.

• Nếu \(X > N\) thì bạn Dũng sẽ đếm số lượng dãy con tăng khác nhau có tổng lớn hơn hoặc bằng \(X\).

Input

Dữ liệu vào từ bàn phím gồm:

• Dòng 1: chứa số nguyên dương \(N\) và \(X\) (\(X \le 10^{18}\)).

• Dòng 2: chứa \(N\) số nguyên dương \(a_1, a_2, \ldots, a_N\) (\(a_i \le 10^9\), \(1 \le i \le N\)).

Ràng buộc:

• Có \(40\%\) số test có \(N \le 10^6\); \(X = 1\); \(X \le N\).

• Có \(40\%\) số test khác có \(N \le 50\); \(2 \le X \le N\).

• Có \(20\%\) số test còn lại có \(2 \le N \le 20\); \(X > N\).

Output

Ghi ra màn hình số nguyên dương duy nhất là kết quả tìm được tương ứng với dữ liệu đầu vào.

Example 1

Input:

6 2
1 2 3 4 6 16

Output:

6

Example 2

Input:

4 6
1 2 3 4

Output:

7

Note

Ví dụ 1: Có \(6\) cách chọn \(2\) số chẵn từ dãy \(a\) là: \(\{2,4\}, \{2,6\}, \{2,16\}, \{4,6\}, \{4,16\}, \{6,16\}\).

Ví dụ 2: Có \(7\) dãy con tăng có tổng lớn hơn hoặc bằng \(6\) là: \(\{1,2,3\}, \{1,2,4\}, \{1,3,4\}, \{2,3,4\}, \{2,4\}, \{3,4\}, \{1,2,3,4\}\).