Sau khi Bờm đáp ứng hết các điều kiện mà Phú Ông đưa ra, Bờm lại thắng cuộc một lần nữa. Vì phần thưởng lần này quá lớn nên Bờm vội chạy về và lục soát khắp nhà mới tìm được một cái ba lô có sức chứa trọng lượng không vượt quá S. Bờm vội vã mang đến nhà Phú Ông nhận thưởng. Phú Ông có N thỏi vàng có trọng lượng lần lượt là a1, a2, …, aN để cho Bờm lựa chọn. Bờm rất cẩn thận lựa chọn các thỏi vàng cho vào ba lô sao cho tổng trọng lượng lớn nhất mà không vượt quá sức chứa của nó.

Yêu cầu: Bạn hãy tính toán giúp Bờm có thể chọn những thỏi vàng để tổng trọng lượng là lớn nhất và đếm có bao nhiêu cách lựa chọn như vậy? (Hai cách chọn là khác nhau nếu khác nhau ít nhất một thỏi vàng).

Dữ liệu: Vào từ tệp văn bản PO.INP có cấu trúc như sau: Dòng đầu gồm 2 số nguyên N và S (0 < N ≤ 1000; 0 < S ≤ 50000; N * S ≤ 5 * 10^6); Dòng thứ hai chứa số nguyên dương Q là loại truy vấn nhận giá trị 1 hoặc 2; Dòng cuối gồm N số nguyên ai (0 < ai ≤ 10^3,1 ≤ i ≤ N).

Kết quả: Đưa ra tệp văn bản PO.OUT có cấu trúc như sau: Với Q = 1 thì chỉ ghi ra tổng trọng lượng lớn nhất có thể. Với Q = 2 thì ghi ra 2 dòng:

• Dòng 1 ghi tổng trọng lượng lớn nhất có thể.
• Dòng 2 ghi số cách Bờm có thể lựa chọn để đạt tổng trọng lượng lớn nhất chia lấy dư cho 10^9+7.

Input 01:

3 4
1
3 1 4

Output 01:

4

Input 02:

3 7
2
4 6 2

Output 02:

6
2

Ràng buộc: Có 60% test ứng với 60% số điểm có S ≤ 1000. Có 40% test ứng với 40% điểm có Q=1, 60% test ứng với 60% điểm có Q=2.