USACO 2015 - Tháng 2 - Hạng Bạc

Anh và Tiên là một đôi bạn thân. Nhân ngày sinh nhật của Tiên, Anh quyết định sẽ tặng cô bạn thân một món quà bất ngờ. Từ một nguồn tin thân cận, Anh biết rằng Tiên rất thích học tiếng Anh và các xâu kí tự đẹp, do đó Anh dự định sẽ mua tặng Tiên xâu kí tự mà cô bạn thích. Không may, sau khi mua xong Anh mới biết rằng Tiên cũng không thích một vài xâu kí tự xấu. Không muốn làm bạn mình buồn, Anh sẽ tạo ra một xâu kí tự mới từ xâu cũ mà không có các xâu kí tự xấu đó. Để làm được điều này, Anh sẽ làm như sau:

Anh đang có một xâu kí tự độ dài \(S\). Anh muốn xóa sự xuất hiện xâu con \(T\) trong \(S\). Để làm điều này, Anh sẽ tìm lần xuất hiện đầu tiên của \(T\) và xóa nó khỏi xâu \(S\), sau đó gộp 2 phần còn lại vào với nhau. Anh sẽ làm như thế cho đến khi trong xâu \(S\) không còn sự xuất hiện của xâu \(T\) nữa. Lưu ý rằng việc xóa một lần xuất hiện có thể tạo ra một lần xuất hiện mới của xâu \(T\) mà trước đó không tồn tại.

Anh không biết rằng liệu xâu \(S\) cuối cùng sau khi thực hiện các thao tác có đủ đẹp để tặng Tiên không. Nếu xâu \(S\) đó không ưng ý thì Anh sẽ mua một xâu khác và thực hiện, thay vì bỏ thời gian ra để thực hiện với xâu cũ. Bạn hãy giúp Anh xác định xâu \(S\) cuối cùng sau khi thực hiện các thao tác là gì nhé.

Input:

• Dòng đầu tiên chứa xâu kí tự \(S\) \((1 \leq |S| \leq 10^6)\)
• Dòng tiếp theo chứa xâu kí tự \(T\) \((1 \leq |T| \leq |S|)\).
• Các kí tự trong xâu \(S\) và \(T\) là các kí tự thường (từ \('a'\) đến \('z'\))

Output:

In ra xâu \(S\) cuối cùng sau khi thực hiện thao tác. Dữ liệu đảm bảo rằng xâu \(S\) cuối cùng không rỗng.

Example

anhnnhihiandtien
nhi

anhandtien

Hôm nay, vì mải lo đi mua trà sữa cho crush mà Bảo Anh đến lớp muộn tận 30 phút. Thầy chủ nhiệm rất không hài lòng và phạt Bảo Anh phải nhảy lò cò quanh sân thể dục của trường. Sân thể dục là một lưới hình chữ nhật có kích thước \(N * M\) ô vuông và Bảo Anh phải nhảy từ ô \((1, 1)\) đến ô \((N, M)\) của sân trường. Thấy việc này quá dễ, Bảo Anh quyết định tăng độ khó cho thử thách. Bảo Anh đánh dấu nhãn các ô vuông bởi các giá trị nguyên có giá trị từ \(1\) đến \(K\) và cậu chỉ có thể nhảy từ ô hiện tại đến một ô khác nếu:

• Nhãn của ô cậu nhảy đến phải khác với nhãn của ô hiện tại.
• Ô mà cậu nhảy đến phải ở bên dưới ít nhất 1 hàng so với ô hiện tại.
• Ô mà cậu nhảy đến phải ở bên phải ít nhất 1 cột so với ô hiện tại.

Cảm thấy cũng chưa đủ khó, Bảo Anh muốn tính xem có bao nhiêu cách nhảy thỏa mãn khác nhau nếu cậu xuất phát từ ô \((1, 1)\) và kết thúc tại ô \((N, M)\). Tuy nhiên, vì đang bận tương tư nên Bảo Anh không thể tập trung giải quyết bài toán, bạn hãy giúp cậu ấy nhé.

INPUT

• Dòng đầu tiên gồm 3 số nguyên dương \(N, M, K\) \((2 \leq N, M \leq 750, 1 \leq K \leq N * M)\)
• \(N\) dòng tiếp theo chứa \(M\) số nguyên dương. Số thứ \(j\) của dòng \(i\) chứa số nguyên dương \(a_i,_j\) \((1 \leq a_i,_j \leq K)\)

OUTPUT

In ra số nguyên là số cách nhảy thỏa mãn khác nhau. Vì đáp số có thể rất lớn, nên bạn cần in kết quả khi chia lấy dư cho \(10^9 + 7\).

VÍ DỤ:

INPUT:

4 4 4
1 1 1 1
1 3 2 1
1 2 4 1
1 1 1 1

OUTPUT:

5

**Ràng buộc: **

• Subtask 1: \(\ 2 \leq N, M \leq 100\)
• Subtask 2: \(\ 2 \leq N, M \leq 750\)

Hàng năm làng LQDOJ tổ chức cho người dân thi đấu giải bóng đá có tên là FOS Champion League. Năm nay có \(N\) đội đăng kí tham dự giải, mỗi đội được gán một \(ID\) riêng biệt. FOS Champion League là giải đấu loại trực tiếp và Flower_On_Stone - phó trưởng làng được quyền quyết định đội thắng cuộc, đội thua cuộc sẽ bị loại khỏi giải đấu. Giải sẽ kết thúc khi chỉ còn một đội vô địch.

Flower_On_Stone nhận thấy một sự trùng lặp ngẫu nhiên trên bảng điểm điện tử trong các trận đấu.Trong bất kỳ trận đấu nào,điểm kết hợp của cả hai đội đấu đúng bằng phép toán XOR trên \(ID\) của hai đội. Ví dụ: Nếu hai đội có \(ID\) là \(12\) và \(20\) đang đấu thì tổng điểm của hai đội là \(28\) vì \((12\) XOR \(20) = 28\).

Chính vì điều thú vị này mà ban tổ chức muốn tổ chức thật nhiều trận đấu sao cho tổng điểm ghi được trong giải FOS Champion League là lớn nhất có thể.

Yêu cầu: Hãy giúp ban tổ chức lên lịch thi đấu sao cho tổng điểm ghi được là lớn nhất có thể.

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) \((2 \le N \le 2000)\).
• \(N\) dòng tiếp theo mỗi dòng chứa \(ID\) của một đội \((1 ≤ ID ≤ 1073741823)\).

Output

• In ra đáp án sau khi thực hiện yêu cầu bài toán.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): Có \(N \le 500\) và \(ID \le 10^5\).
• Subtask \(2\) (\(80\%\) số điểm): Không có ràng buộc gì thêm.

Example

4
3
6
9
10

37