Bài tập

Hãy tìm tất cả các số nguyên tố trong đoạn [\(A;B\)]

Input

• Gồm 2 số nguyên \(A;\ B\) cách nhau bởi 1 dấu cách (\(1\leq A\leq B\leq 10^7\))

Output

• Ghi ra tất cả các số nguyên tố trong khoảng [\(A;B\)]. Mỗi số trên 1 dòng.

Example

1 10

2
3
5
7

Cho tập hợp \(S\) gồm \(n\) xâu kí tự: \(S_1, S_2, \dots, S_n\). Kí tự trong các xâu này có thể là a hoặc b.

Một xâu \(A\) được gọi là xâu hoán vị của xâu \(B\), nếu ta có thể tạo ra được xâu \(A\) bằng cách sắp xếp lại các kí tự của xâu \(B\). Hãy tạo tập hợp \(S'\) theo nguyên tắc sau: với mỗi xâu \(S_i\) \((1 \le i \le n)\), ta thêm tất cả các xâu hoán vị của \(S_i\) vào \(S'\). Nói cách khác, \(S'\) là tập hợp các xâu hoán vị của \(n\) xâu thuộc \(S\).

Ta tiến hành dựng cây trie của tập xâu \(S'\) vừa tạo. Hãy cho biết cây trie này có bao nhiêu nút.

Nhắc lại về Trie

**Trie** là một cấu trúc dữ liệu dạng cây dùng để lưu trữ một danh sách các xâu với bộ kí tự hữu hạn, cho phép việc lưu trữ các xâu hiệu quả có tiền tố giống nhau.

Cây trie được dựng theo nguyên tắc: mỗi nút liên kết với một xâu ký tự sao cho các xâu ký tự của tất cả các nút con của một nút đều có chung một tiền tố, chính là xâu ký tự của nút đó. Nút gốc tương ứng với xâu ký tự rỗng.

Ví dụ, với các xâu `aba`, `abb`, `acb`, ta dựng được một cây trie gồm $7$ nút như sau:

\begincenter

\endcenter

Input

• Dòng đầu tiên chứa số nguyên \(n\) \((1 \leq n \leq 20)\) là số lượng xâu trong tập \(S\).

• Trong \(n\) dòng tiếp theo, dòng thứ \(i\) chứa xâu \(S_i\) \((1 \le |S_i| \le 10^5)\), các kí tự của xâu chỉ có thể là a hoặc b.

Output

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

Example

1
abaa

14

2
abb
aaa

11

4
aa
ab
bb
aba

10

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(|S_i| \leq 20\).

• Subtask \(2\) (\(20\%\) số điểm): \(n = 1, |S_i| \leq 10^3\).

• Subtask \(3\) (\(15\%\) số điểm): \(n = 2, |S_i| \leq 10^3\).

• Subtask \(4\) (\(10\%\) số điểm): \(|S_i| \leq 10^3\).

• Subtask \(5\) (\(15\%\) số điểm): \(n = 1\).

• Subtask \(6\) (\(10\%\) số điểm): \(n = 2\).

• Subtask \(7\) (\(10\%\) số điểm): Không có ràng buộc gì thêm.

Sau khi tìm ra mật khẩu là một xâu \(S\) có \(N\) kí tự, An quyết định mua một bàn phím chuyên dụng để nhập mật khẩu này. Do mật khẩu chỉ dùng \(M\) chữ cái đầu tiên trong bảng chữ cái tiếng Anh nên bàn phím chỉ cần \(M\) phím tương ứng. Do sở thích nên An bố trí tất cả \(M\) phím lên cùng một hàng, ví dụ với \(M\) \(=\) \(3\), có \(6\) cách bố trí khác nhau là : \(abc\), \(acb\), \(bac\), \(bca\), \(cab\), \(cba\).

An có thói quen nhập mật khẩu bằng đầu chiếc bút để ấn phím nên thời gian di chuyển từ \(S_{i}\) sang \(S_{i + 1}\) sẽ bằng khoảng cách giữa hai kí tự này trên bàn phím. Như vậy, tổng thời gian nhập là \(\sum_{i = 1}^{n - 1} (pos(S_{i}) - pos(S_{i + 1}))\), trong đó \(pos(c)\) là vị trí của kí tự \(c\) trên bàn phím. Ví dụ nếu xâu \(S\) là xâu \(aacabc\) và bàn phím được bố trí là \(bac\) thì tổng thời gian di chuyển là \(|2 - 2| + |2 - 3| + |3 - 2| + |1 - 2| + |1 - 3| = 5\).

Yêu cầu: Hãy tìm cách bố trí bàn phím sao cho tổng thời gian di chuyển là nhỏ nhất.

Input

Dòng đầu ghi \(2\) số nguyên dương \(N\) và \(M\) cách nhau một dấu cách.

Dòng thứ hai ghi \(N\) kí tự của xâu \(S\).

Output

Tổng thời gian di chuyển nhỏ nhất.

Example

6 3
aacabc

5

Scoring

Có \(20\%\) số test có \(N \leq 100\), \(M \leq 2\).

Có \(20\%\) số test có \(N \leq 100\), \(M \leq 10\).

Có \(30\%\) số test có \(N \leq 100000\), \(M \leq 10\).

Có \(30\%\) số test có \(N \leq 100000\), \(M \leq 20\).

Cho dãy số nguyên \(A\) gồm \(N\) phần tử \(A_{1}, A_{2}, \ldots, A_{N}\) và một số nguyên \(K\).

Yêu cầu: Đếm số cặp số \(L, R\) \((1 \leq L \leq R \leq N)\) sao cho dãy con liên tiếp \(A_{L}, A_{L + 1}, \ldots, A_{R}\) có hiệu giữa số lớn nhất và số nhỏ nhất không vượt quá \(K\).

Input

• Dòng đầu tiên gồm hai số nguyên dương \(N, K\) \((N \leq 10^{5}, K \leq 10^{18})\)

• Dòng thứ hai gồm \(N\) số nguyên dương \(A_{1}, A_{2}, \ldots, A_{N}\) \((|A_{i}| \leq 10^{9})\).

Output

• In ra một số nguyên duy nhất là kết quả của bài toán.

Example

5 2
2 -1 3 1 3

8

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N \leq 100\).

• Subtask \(2\) (\(20\%\) số điểm): \(N \leq 5000\).

• Subtask \(3\) (\(30\%\) số điểm): không có ràng buộc gì thêm.