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à a₁, a₂, …, a_N để 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:

+ Dòng đầu gồm 2 số nguyên N và S (0 < N ≤ 1000; 0 < S ≤ 50000; N × S ≤ 5 × 10⁶);

+ 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 a_i (0 < \(a\)_i\(\ \leq \ 10\)³\(,1\ \leq \ i\ \leq \ N)\mathbf{.}\)

Kết quả:

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⁹+7.

Ví dụ:

Ràng buộc:

+ Có 60% test ứng với 60% số điểm có S ≤ 1000. (40% test ứng với 40% điểm có Q=1, 60% test ứng với 60% điểm có Q=2).