Tin học trẻ B - Vòng Khu vực miền Bắc 2022

Lê có \(n\) hạt cườm, hạt thứ \(i\) (\(1 \le i \le n\)) có mã màu là \(c_i\). Lê muốn chọn ra đúng \(m\) (\(m < n\)) hạt để làm một vòng tay. Vì rất yêu thích số \(s\) nên Lê muốn đếm xem có bao nhiêu cách chọn \(m\) hạt mà tổng giá trị các mã màu đúng bằng \(s\). Hai cách được gọi là khác nhau nếu tồn tại một hạt được chọn trong cách này nhưng không thuộc trong cách kia.

Yêu cầu

Cho các số nguyên dương \(c_1, c_2, \dots, c_n\) là mã màu của \(n\) hạt cườm và hai số nguyên dương \(m, s\), hãy đếm số cách chọn \(m\) hạt để tổng giá trị các mã màu của các hạt được chọn bằng \(s\).

Input

Dữ liệu vào từ thiết bị vào chuẩn có khuôn dạng:

• Dòng đầu tiên gồm ba số nguyên \(n, m, s\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(c_1, c_2, \dots, c_n\) (\(1 \le c_i \le 10^9\)).

Output

• Ghi ra thiết bị ra chuẩn một dòng chứa một số nguyên là số cách chọn thỏa mãn.

Example

5 4 10
2 2 3 2 3

3

Ràng buộc

• Có \(30\%\) số test ứng với \(30\%\) số điểm của bài thỏa mãn: \(m = n - 1; n \le 18\).
• \(40\%\) số test khác ứng với \(40\%\) số điểm của bài thỏa mãn: \(n \le 18\).
• \(30\%\) số test còn lại ứng với \(30\%\) số điểm của bài thỏa mãn: \(n \le 36\).

Lê xếp \(n\) hạt cườm thành một vòng tròn theo chiều kim đồng hồ, ban đầu, các hạt có mã màu lần lượt tương ứng là \(a_1 = 0, a_2 = 0, \dots, a_n = 0\). Lê có hai loại lệnh để thay đổi mã màu như sau:

• Lệnh \(D \ i\): gấp đôi mã màu của một hạt, cụ thể: \(a_i = a_i \cdot 2\), lệnh này chỉ được thực hiện nếu \(a_i > 0\);
• Lệnh \(P \ i\): gấp đôi và thêm \(1\) vào mã màu của hai hạt kề nhau, cụ thể: \(a_i = a_i \cdot 2 + 1\) và \(a_j = a_j \cdot 2 + 1\), trong đó \(j\) là hạt kề tiếp theo của hạt \(i\) theo chiều kim đồng hồ.

Lê muốn tìm cách thay đổi dãy mã màu ban đầu (tất cả đều bằng \(0\)) về trạng thái yêu thích bằng cách dùng hai loại lệnh trên.

Yêu cầu

Cho dãy số nguyên không âm \(b_1, b_2, \dots, b_n\), hãy giúp Lê đếm số cách thay đổi dãy mã màu ban đầu về dãy mã màu \(b_1, b_2, \dots, b_n\) (hai cách được gọi là khác nhau nếu số bước sử dụng khác nhau hoặc ở bước thứ \(t\) của cách này sử dụng lệnh khác với lệnh thứ \(t\) của cách kia).

Input

• Dòng đầu tiên gồm số nguyên \(n\);
• Dòng thứ hai chứa \(n\) số nguyên không âm \(b_1, b_2, \dots, b_n\) (\(1 \le b_i \le 10^9\)).

Output

• Ghi ra thiết bị ra chuẩn một dòng chứa một số là phần dư khi chia số cách thực hiện được cho \(10^9 + 7\).

Example

3
1 3 2

3

Scoring

• Có \(25\%\) số test ứng với \(25\%\) số điểm của bài có \(n = 3\) và \(b_i \le 3\);
• Có \(25\%\) số test khác ứng với \(25\%\) số điểm của bài có \(n = 3, b_i \le 30\);
• Có \(25\%\) số test khác ứng với \(25\%\) số điểm của bài có \(n \le 5, b_i \le 1000\);
• Có \(25\%\) số test còn lại ứng với \(25\%\) số điểm của bài có \(n \le 5, b_i \le 10000\).