Bài tập

Cho xâu \(S\) gồm các chữ cái viết thường. Hãy tìm số lượng kí tự ít nhất cần thêm vào xâu \(S\) để \(S\) trở thành xâu đối xứng.

Một xâu được gọi là đối xứng nếu đọc xuôi hay đọc ngược đều giống nhau.

\InputFile

• Một dòng duy nhất chứa xâu \(S\) gồm các chữ cái viết thường. (\(1 \le |S| \le 1000\))

\OutputFile
In ra một số nguyên duy nhất là số lượng kí tự ít nhất phải thêm.

\Examples

\beginexample
\exmp
abcbce

2

\endexample

\endproblem

Trong tương lai xa, con người đã chế tạo thành công một loại tàu thăm dò vũ trụ tiên tiến. Tàu này được thiết kế để di chuyển trong một không gian một chiều, và độ cao của nó so với một mốc chuẩn được biểu diễn bằng một số nguyên không âm. Phi công tài năng của con tàu, tên là Lập, phải điều khiển con tàu để nó di chuyển từ độ cao ban đầu \(h_1\) đến một độ cao mục tiêu \(h_2\) trong đúng \(n\) giây.

Tại mỗi giây, Lập có thể thực hiện một trong ba lệnh điều khiển sau:

• Tăng độ cao lên 1 đơn vị.
• Giảm độ cao đi 1 đơn vị.
• Giữ nguyên độ cao.

Con tàu có thể chạm vào điểm mốc (độ cao 0), nhưng tuyệt đối không được đạt độ cao âm.

Hai cách điều khiển được coi là khác nhau nếu có ít nhất một thời điểm \(i\) (\(1 \le i \le n\)) mà lệnh điều khiển trong hai cách đó là khác nhau. Nhiệm vụ của bạn là giúp Lập đếm xem có bao nhiêu cách điều khiển khác nhau để hoàn thành nhiệm vụ này.

Input

• Dòng duy nhất chứa ba số nguyên không âm \(h_1, h_2, n\) (\(0 \le h_1, h_2, n \le 10^5\)).

Output

• In ra số cách điều khiển tìm được, lấy phần dư khi chia cho \(10^9 + 7\).

Example

0 0 6

51

Nhóm bạn của Tuấn đang đi dã ngoại và bất ngờ gặp một con sông lớn. Tổng cộng có \(n\) người trong nhóm, bao gồm cả Tuấn. May mắn thay, có một con thuyền nhỏ ở ngay bờ sông. Con thuyền này có thể chở một lúc một nhóm người với tổng trọng lượng tối đa là \(k\) kilogam.

Để tính toán số lượt di chuyển, Tuấn đã thống kê trọng lượng của mọi người trong nhóm. Kết quả cho thấy mỗi người có trọng lượng là 50 hoặc 100 kilogam. Bây giờ, Tuấn muốn tìm số lượt di chuyển tối thiểu để đưa tất cả mọi người sang bờ bên kia. Con thuyền cần ít nhất một người để điều khiển nó từ bờ này sang bờ kia. Mỗi lần di chuyển, thuyền có thể chở bất kỳ số người nào (lớn hơn 0), miễn là tổng trọng lượng của họ không vượt quá \(k\).

Ngoài ra, Tuấn còn thắc mắc có bao nhiêu cách để đưa mọi người sang bờ bên kia trong số lượt di chuyển tối thiểu đó. Hai cách được coi là khác nhau nếu trong một lượt di chuyển nào đó, tập hợp người trên thuyền cách này khác tập hợp người trên thuyền của cách kia. Tuy nhiên, không phải lúc nào Tuấn cũng thắc mắc câu hỏi này, chính vì vậy, Tuấn đã cung cấp một số nguyên dương \(T\) \((1 \leq T \leq 2)\). Nếu \(T = 2\), Tuấn sẽ thắc mắc số lần di chuyển ít nhất và số cách để đưa sang bờ bên kia với số lần di chuyển ít nhất. Nếu \(T = 1\), Tuấn chỉ hỏi rằng số lượt di chuyển ít nhất là bao nhiêu.

Yêu cầu: Hãy giúp Tuấn giải quyết bài toán này.

Input

• Dòng đầu tiên chứa số nguyên dương \(T\) \((1 \leq T \leq 2)\).
• Dòng đầu tiên chứa hai số nguyên \(n, k\) (\(1 \le n \le 50, 1 \le k \le 5000\)) lần lượt là số người trong nhóm và giới hạn trọng lượng của thuyền.
• Dòng tiếp theo chứa \(n\) số nguyên là trọng lượng của từng người, mỗi người có trọng lượng là 50 hoặc 100 kilogam.
• Bạn có thể coi Tuấn và các bạn của anh ấy được đánh số theo một thứ tự nào đó.

Output

• Dòng đầu tiên in ra một số nguyên là số lượt di chuyển tối thiểu. Nếu không thể đưa tất cả mọi người sang bờ bên kia, in ra \(-1\).
• Nếu \(T = 2\), in ra dòng thứ hai chính là phần dư của số cách di chuyển trong số lượt tối thiểu sau khi chia cho \(1000000007\) (\(10^9 + 7\)). Nếu không thể di chuyển, in ra \(0\).

Example

1
1 50
50

1

2
3 100
50 50 100

5
2

2
2 50
50 50

-1
0

Scoring

• Subtask 1 (20% số điểm) : \(T = 1\), tất cả người trên thuyền đều có trọng lượng bằng nhau.
• Subtask 2 (20% số điểm) : \(T = 1, n \leq 3\).
• Subtask 3 (20% số điểm) : \(T = 1, n \leq 10\).
• Subtask 4 (20% số điểm) : \(T = 2, n \leq 100\).
• Subtask 5 (20% số điểm) : không có ràng buộc gì thêm.

Cho dãy số nguyên dương \(A\) gồm \(n\) phần tử.
Hãy đếm số lượng dãy con (không nhất thiết liên tiếp) có trung bình cộng bằng đúng \(k\).

Input

Vào từ file văn bản DAYCON.INP:

• Dòng 1: số bộ test \(T \le 10\).

• Mỗi test gồm:

• Một dòng: \(n, k\) (\(1 \le n, k \le 200\)).

• Một dòng: \(a_1, a_2, \dots, a_n\) với \(1 \le a_i \le 200\).

Output

Ghi ra file văn bản DAYCON.OUT:

Với mỗi test, in ra một dòng --- số lượng dãy con có trung bình bằng \(k\), modulo \(10^9 + 7\).

Example

3
4 6
5 7 6 7
5 100
4 2 5 10 5
6 100
77 97 114 105 115 97

5
0
1

Scoring

• Subtask 1 (20%): \(n \le 16\), \(k, a_i \le 50\).
• Subtask 2 (40%): \(n \le 30\), \(k, a_i \le 50\).
• Subtask 3 (40%): Không có ràng buộc thêm.