Contest ôn thi HSG 9-10 (số 5)

Bạn QuanNgokNgek đang học mẫu giáo. Cô giáo Thiên Thảo đưa cho Quân một xâu ký tự \(S\), Quân có thể sử dụng những chữ cái có trong xâu \(S\) để tạo ra các từ mới. Hỏi Quân có thể tạo ra bao nhiêu từ \(T\) từ những chữ cái có trong xâu \(S\).

Input

• Dòng đầu tiên chứa xâu \(S\) chỉ gồm các kí tự in thường (\(1 \le |S| \le 10^6\))
• Dòng thứ hai chứa xâu \(T\) chỉ gồm các kí tự in thường (\(1 \le |T| \le 10^6\))

Output

• Ghi ra đáp án bài toán.

Example

cabaacbcb
abc

3

Ràng buộc

• 100% số lượng test giới hạn như đề bài

Trong đất nước Ý, có \(n\) công ty bán pizza đế mỏng viền phô mai vị hải sản sốt rau củ phủ thêm nhiều phô mai nóng hổi. Những công ty này được đánh dấu từ \(1\) đến \(n\), công ty thứ \(i\) có tầm hoạt động là một hình chữ nhật có đỉnh trên bên trái là \((x[i], y[i])\) và đỉnh dưới bên phải là \((u[i], v[i])\). Những công ty cạnh tranh với nhau khi có tầm hoạt động giao nhau. Hỏi có bao nhiêu cặp công ty đang cạnh tranh với nhau?

Input

• Dòng đầu tiên chứa một số nguyên \(n\) (\(1 \le n \le 10^3\)).
• \(n\) dòng tiếp theo, dòng thứ \(i + 1\), chứa \(4\) số nguyên không âm \(x[i], y[i], u[i], v[i]\). Trong đó không có số nào lớn hơn \(10^9\).

Output

• Kết quả bài toán.

Ràng buộc

• \(50\%\) số lượng test \(x[i], y[i], u[i], v[i] \le 100\).
• \(50\%\) số lượng test không giới hạn gì thêm.

Example

5
1 2 2 1
2 3 4 2
3 4 4 1
1 1 3 0
5 5 6 4

4

(Các điểm khác nhau giữa bài 2 và bài 3 là giới hạn \(n\), \(a[i]\) và số mod)

Canuc80k có \(3\) người con: Minh, Sam và Ngọc. Ông giành tình thương cho cả ba như nhau. Biết mình đã có tuổi, chẳng sống được lâu nữa. Trước lúc lâm chung, ông muốn chia gia tài cho những người con của mình. Tài sản của ông chẳng có gì ngoài vài mảnh đất hai mặt tiền bên quận 1 Sài Gòn. Đánh số các mảnh đất từ \(1\) đến \(n\), mảnh đất thứ \(i\) sẽ có diện tích là \(a_i\) \(\text{km}^2\). Khi chia gia tài, ông muốn sao cho Ngọc có nhiều diện tích đất nhất, còn hai người con trai sẽ được chia bằng nhau. Tính số cách chia khác nhau mà Canuc80k có thể thực hiện. \(2\) cách chia được coi là khác nhau khi tồn tại một mảnh ruộng \(i\) được chia cho người \(X\) ở cách thứ nhất nhưng chia cho người \(Y\) ở cách thứ \(2\) (\(X \neq Y\)).

Input

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

• Dòng đầu tiên chứa số nguyên dương \(n\) (\(n \le 19\))
• Dòng tiếp theo chứa các số nguyên dương \(a_1, a_2, \ldots, a_n\) (\(a_i \le 10^{12}\))

Output

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

• Kết quả bài toán

Ràng buộc

• \(25\%\) số lượng test \(n \le 15\)
• \(25\%\) số lượng test \(n \le 17\)
• \(30\%\) số lượng test \(n \le 18\)
• \(20\%\) số lượng test không giới hạn gì thêm

Example

3
100000000 1 1

3

(Bạn cần đọc đề bài 2 trước khi đọc bài này)
(Các điểm khác nhau giữa bài 2 và bài 3 là giới hạn \(n\), \(a[i]\) và số mod)

Sau khi viết di chúc xong, Canuc80k đã sẵn sàng nhắm mắt. Tiếc là đã qua nhiều thập kỉ, ông vẫn còn sống khỏe. Đến khi tròn 99 tuổi, sau khi nghe đứa cháu ngoại chúc "Chúc ông sống lâu trăm tuổi", ông biết rằng đã đến lúc để viết lại một chiếc di chúc khác. Chỉ có một điểm khác biệt là, những năm qua, ông đã kiếm được thêm rất nhiều mảnh đất nữa. Vì đáp án có thể rất lớn nên cần in ra kết quả sau khi chia lấy dư cho \(10^9 + 7\).

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) (\(n \le 100\)).
• Dòng tiếp theo chứa các số nguyên dương \(a_1, a_2, \ldots, a_n\) (\(a_i \le 20\)).

Output

• Ghi ra một số nguyên duy nhất là đáp án của bài toán sau khi chia lấy dư cho \(10^9 + 7\).

Ràng buộc

• \(30\%\) số lượng test có \(n \le 19\) và tổng tất cả các số trong mảng \(a[]\) không lớn hơn \(200\).
• \(40\%\) số lượng test có tổng tất cả các số trong mảng \(a[]\) không lớn hơn \(200\).
• \(30\%\) số lượng test không giới hạn gì thêm.

Example

3
20 1 1

3