Knapsack 2

Anh Khoai được ông phú hộ hứa gả con gái với điều kiện làm việc không công cho ông ta mười năm và phải hoàn thành một nhiệm vụ ông ta giao cho. Sau mười năm làm việc anh Khoai tìm ông phú hộ để nhận nhiệm vụ cuối cùng. Vì không muốn gả con gái cho anh Khoai nên phú hộ yêu cầu anh mang về cho ông cây tre trăm đốt. Với sự giúp đỡ của ông bụt, anh Khoai đã mang về một trăm đốt tre cùng hai câu thần chú “khắc nhập” và “khắc xuất” để hoàn thành nhiệm vụ. Tuy nhiên, bằng cách nào đó ông phú hộ đã biết được sự việc và chuẩn bị sẵn rất nhiều đốt tre dài ngắn khác nhau và yêu cầu anh tạo thành cây tre có độ dài \(K\) từ những đốt tre đã có sẵn thì ông ta mới gả con gái cho.

Yêu cầu: Hãy giúp anh Khoai kiểm tra xem có bao nhiêu cách tạo ra cây tre có độ dài \(K\) từ những đốt tre đã có sẵn.

Input

Đọc từ file văn bản TRE.INP có cấu trúc như sau:

• Dòng đầu tiên chứa 2 số nguyên là \(N\) và \(K\ (1 \le N, K \le 10^5)\) trong đó \(N\) là số đốt tre, \(K\) là chiều dài cây tre cần tạo thành.
• Dòng 2 chứa \(N\) số nguyên dương \(A_1, A_2, ..., A_n\) cách nhau một dấu cách lần lượt là chiều dài của \(N\) đốt tre \((A_i \le 10^5)\).

Output

Ghi ra file văn bản TRE.OUT một số duy nhất là số cách tạo thành cây tre có độ dài \(K\), chỉ cần in ra kết quả sau khi chia lấy dư cho \(10^9 + 7\).

Scoring

• Subtask \(1: 20\%\) test có \(N \le 10^2\).
• Subtask \(2: 40\%\) test có \(N \le 10^3\).
• Subtask \(3: 40\%\) giới hạn gốc.

Example

6 90
70 50 60 20 30 40

4

Một nhà hàng bánh ngọt có 3 loại bánh: bánh táo, bánh xoài và bánh răng. Loan muốn đặt trước n chiếc bánh. Vì cô là một khách hàng kỹ tính nên muốn bữa ăn của mình thõa mãn thêm 2 điều kiện: số lượng bánh táo phải chia hết cho 2 và số lượng bánh xoài phải chia hết cho 3.

Loan sẽ thưởng thức từng chiếc bánh một. Hai cách thưởng thức bánh được coi là khác nhau nếu như chiếc bánh thứ \(i\) \((1 \leq i \leq n)\) Loan ăn là hai chiếc bánh khác nhau.
Ví dụ:

Cách thưởng thức 1: Loan ăn 2 bánh táo, 1 bánh răng, 3 bánh xoài

Cách thưởng thức 2: Loan ăn 2 bánh táo, 3 bánh xoài, 1 bánh răng

Vậy hai cách thưởng thức trên là khác nhau vì chiếc bánh thứ 3 mà Loan ăn ở cách thứ nhất là bánh răng, còn ở cách thứ hai là bánh xoài.

Input:

Một số nguyên dương \(n\) \((1 \leq n \leq 10^6)\), là số lượng bánh Loan đặt

Output:

Số lượng cách thưởng thức bánh khác nhau của Loan. Vì đây là một số rất lớn nên chỉ cần in ra kết quả sao khi chia lấy dư cho \(10^9 + 7\).

Ví dụ:

Input:

3

Output:

5

Input:

10

Output:

9882

Giải thích ví dụ:

Ở ví dụ thứ nhất, có 5 cách thưởng thức thỏa mãn: (Bánh răng, Bánh răng, Bánh răng), (Bánh xoài, Bánh xoài, Bánh xoài), (Bánh táo, Bánh táo, Bánh răng), (Bánh răng, Bánh táo, Bánh táo), (Bánh táo, Bánh răng, Bánh táo).

Thuận có một dãy đèn gồm đèn, các đèn được đánh số từ \(1\) đến \(n\). Mỗi đèn có ba trạng thái, trạng thái sáng màu xanh hoặc sáng màu đỏ hoặc tắt. Ban đầu tất cả các đèn đều ở trạng thái tắt. Tương ứng với đèn thứ có công tắc thứ \(i (1 \le i \le n)\), khi tác động vào công tắc này trạng thái đèn thứ \(i\) sẽ thay đổi như sau:

• Nếu đèn đang ở trạng thái tắt sẽ chuyển sang trạng thái sáng màu xanh;
• Nếu đèn đang ở trạng thái sáng màu xanh sẽ chuyển sang trạng thái sáng màu đỏ;
• Nếu đèn đang ở trạng thái sáng màu đỏ sẽ chuyển sang trạng thái tắt.

Thuận đã thực hiện một dãy gồm \(t\) lần tác động vào các công tắc và nhận được dãy đèn gồm \(a\) đèn ở trạng thái sáng màu xanh và \(b\) đèn ở trạng thái sáng màu đỏ. Là người yêu thích Tin học, Thuận muốn tính xem có bao nhiêu dãy gồm đúng \(t\) thao tác để từ trạng thái ban đầu (tất cả các đèn ở trạng thái tắt), sau khi thực hiện dãy thao tác có \(a\) đèn ở trạng thái sáng màu xanh và \(b\) đèn ở trạng thái sáng màu đỏ.

Yêu cầu: Cho các số nguyên \(n, t, a, b\), gọi là số dãy gồm thao tác để từ trạng thái ban đầu nhận được dãy có \(a\) đèn ở trạng thái sáng màu xanh và \(b\) đèn ở trạng thái sáng màu đỏ. Hãy tính \(S \% (10^9 + 7)\), trong đó \(\%\) là phép toán chia lấy dư.

Input

Vào từ thiết bị vào chuẩn gồm một dòng chứa bốn số nguyên \(n, t, a, b\) cách nhau bởi dấu cách \((0 \le a, b; a + b \le n)\);

Output

• Ghi ra thiết bị ra chuẩn một số nguyên duy nhất là giá trị \(S \% (10^9 + 7)\)

Scoring

• Subtask #1 (\(30\%\) số điểm): \(n, t \le 6\);
• Subtask #2 (\(30\%\) số điểm): \(n, t \le 60\);
• Subtask #3 (\(40\%\) số điểm): \(n, t \le 600\);

Example

2 3 1 1

6

1, 1, 2
1, 2, 1
1, 2, 2
2, 1, 1
2, 1, 2
2, 2, 1

Trong buổi giao lưu giữa các thí sinh của kì thi Tin học trẻ, có học sinh xếp thành một hàng, học sinh đứng thứ \(i(1 \leq i \leq n)\) đến từ tỉnh có mã là số nguyên \(c_i(1 \leq c_i \leq 63)\). Ban tổ chức muốn tách hàng để nhận được \(g\) nhóm học sinh tham gia một trò chơi. Cụ thể, Ban tổ chức cần chọn ra \(g - 1\) điểm cắt \(1 < k_1 < k_2 ... < k_{g-1} < n\), khi đó các bạn từ đầu hàng đến bạn đứng thứ \(k_1\) sẽ xếp vào nhóm thứ nhất, các bạn đứng thứ \(k_1 + 1\) đến \(k_2\) sẽ xếp vào nhóm thứ hai,..., bạn đứng thứ \(k_{g-1} + 1\) đến \(n\) xếp vào nhóm thứ \(g\). Độ phong phú của một nhóm được tính bằng số lượng tỉnh khác nhau của học sinh trong nhóm. Để các thí sinh có nhiều cơ hội giao lưu với nhau, Ban tổ chức muốn tìm cách tách hàng \(g\) thành nhóm để tổng độ phong phú của \(g\) nhóm là lớn nhất.

Yêu cầu: Cho dãy số nguyên dương \(c_1, c_2, ..., c_n\) và số nguyên dương \(g\), hãy tìm cách tách hàng thành \(g\) nhóm để tổng độ phong phú của nhóm là lớn nhất.

Input

• Dòng đầu tiên chứa các số nguyên \(n, g\);
• Dòng thứ hai chứa n số nguyên dương \(c_1, c_2, ..., c_n\).

Output

• Ghi ra một dòng chứa một số là tổng độ phong phú của \(g\) nhóm là lớn nhất tìm được.

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(n \leq 1000; g = 2\)
• Subtask \(2\) (\(25\%\) số điểm): \(n \leq 1000; g = 3\)
• Subtask \(3\) (\(25\%\) số điểm): \(n \leq 1000; g \leq 30\)
• Subtask \(4\) (\(25\%\) số điểm): \(n \leq 10^5; g \leq 30\)

Example

5 2
1 2 1 3 3 

4

Cho một cân hai đĩa và \(n\) quả cân có khối lượng đôi một khác nhau \(w_1, w_2, . . , w_n\). Tiến hành đặt lần
lượt từng quả cân lên một trong hai đĩa của cân và đảm bảo rằng tổng khối lượng bên trái luôn nhỏ
hơn hoặc bằng tổng khối lượng bên phải.

Yêu cầu: Cho \(n\) quả cân có khối lượng \(w_1, w_2, . . , w_n\), hãy đếm số cách xếp \(n\) quả cân thỏa mãn.

Hai cách được gọi là khác nhau nếu thứ tự xếp các quả cân khác nhau hoặc tồn tại một quả cân nằm
ở đĩa khác nhau.

Input

Vào từ thiết bị vào chuẩn có khuôn dạng:

• Dòng 1: chứa số nguyên \(n\);
• Dòng 2: chứa \(n\) số nguyên dương \(w_1, w_2, . . , w_n\).

Output

• Ghi ra thiết bị ra chuẩn một dòng chứa một số nguyên là số cách xếp \(n\) quả cân lên đĩa.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(n \le 7\) và \(w_i \le 1000 (1 \le i \le n)\);
• Subtask \(2\) (\(40\%\) số điểm): \(n \le 14\) và \(w_i \le 1000 (1 \le i \le n)\);
• Subtask \(3\) (\(20\%\) số điểm): \(n \le 28\) và \(w_i = 2^{i−1} (1 \le i \le n)\).

Example

2
1 2

3

3
10 11 12

15