Bài tập

Cho một xâu kí tự \(s\) chứa các kí tự "a", "b", "c", và "?".

Gọi số lượng kí tự "?" trong xâu \(s\) là \(k\). Mỗi dấu "?" trong xâu ta có thể thay thế bằng \(1\) trong \(3\) kí tự "a", "b", "c". Như vậy, có thể tạo ra \(3^k\) xâu chỉ chứa các kí tự "a", "b", "c". Ví dụ, xâu \(s\) = "ac?b?c" ta có thể tạo ra được \(9\) xâu ["acabac", "acabbc", "acabcc", "acbbac", "acbbbc", "acbbcc", "accbac", "accbbc", "accbcc"].

Yêu cầu: Đếm tất cả các xâu con "abc" xuất hiện trong tất cả các xâu có thể tạo ra. In ra kết quả theo modulo \(10^9 + 7\).

Nhắc lại: Xâu con là xâu có thể thu được bằng cách xóa các kí tự ở một số các vị trí trong xâu. Xâu con của xâu "abc" là: ["", "a", "b", "c", "ab", "ac", "bc", "abc"].

Input

Dòng đầu tiên là số nguyên dương \(n\) - độ dài xâu \(s\).

Dòng thứ hai là xâu \(s\) chỉ chứa các kí tự "a", "b", "c", "?".

Output

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

Example

6
ac?b?c

24

Scoring

\(20\%\) số test có \(n \leq 10\).

\(20\%\) số test có \(n \leq 50\).

\(20\%\) số test có \(n \leq 1000\).

\(20\%\) số test đảm bảo xâu \(s\) không có kí tự "?" nào.

\(20\%\) số test cos \(n \leq 200000\).

Cho dãy số nguyên dương \(a_{1}, a_{2}, a_{3}, ..., a_{n}\). Một bộ ba \((i, j, k)\) được gọi là đẹp của dãy \(A\) đã cho nếu thoả mãn:

• \(1 ≤ i ≤ j < k ≤ N\).

• Gọi dãy con liên tiếp \(A_{i}, A_{i + 1}, ... , A_{j}\) là \(X\) và dãy con liên tiếp \(A_{j + 1}, A_{j + 2}, ... , A_{k}\) là \(Y\) thì hai dãy này thoả mãn:

✓ Với mỗi giá trị xuất hiện trong dãy \(X\) thì cũng xuất hiện trong dãy \(Y\).

✓ Với mỗi giá trị xuất hiện trong dãy \(Y\) thì cũng xuất hiện trong dãy \(X\).

Yêu cầu: Cho dãy số \(A\) hãy đếm số bộ ba đẹp \((i, j, k)\) của dãy số này.

Input

• Dòng đầu chứa số nguyên \((1 ≤ N ≤ 2 × 10^5)\).

• Dòng thứ hai chứa \(n\) số nguyên \(A_{i}\) \((1 ≤ A_{i} ≤ N)\).

Output

Ghi ra một số nguyên là số lượng bô ba đẹp của dãy đã cho.

Example

7
3 1 2 1 2 3 1

4

Scoring

Subtask \(1\) (\(20\) điểm): \(N ≤ 500\).

Subtask \(2\) (\(20\) điểm): \(N ≤ 5000\).

Subtask \(3\) (\(20\) điểm): \(A_{i} ≤ 50\).

Subtask \(4\) (\(20\) điểm): Mỗi giá trị xuất hiện đúng hai lần.

Subtask \(5\) (\(20\) điểm): Không có ràng buộc gì thêm.

Số tự nhiên \(m\) được gọi là ước nguyên tố của số nguyên dương \(n\) nếu \(n\) chia hết cho \(m\) và \(m\) là số nguyên tố.

Yêu cầu: Cho \(Q\) truy vấn, mỗi truy vấn gồm ba số nguyên \(a,b,k\). Với mỗi truy vấn, hãy xác định số lượng các số nguyên \(x\) thỏa mãn: \(a \le x \le b\) và có số lượng ước nguyên tố không nhỏ hơn \(k\).

Input

Vào từ tệp văn bản BAI2.INP có cấu trúc:

• Dòng thứ nhất chứa số nguyên dương \(Q\) là số lượng truy vấn \((1 \le Q \le 10^5)\).
• \(Q\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(a,b,k\) \((1 \le a \le b \le 10^6; 0 \le k \le 7)\).

Output

Ghi ra tệp văn bản BAI2.OUT gồm \(Q\) dòng, mỗi dòng ghi một số nguyên duy nhất là kết quả tương ứng với mỗi truy vấn.

Example

1
25 30 2

3

Scoring

• Có \(60\%\) số test ứng với \(60\%\) số điểm của bài thỏa mãn: \(Q = 1\); \(1 \le a \le b \le 10^3\).
• Có \(20\%\) số test khác ứng với \(20\%\) số điểm của bài thỏa mãn: \(Q = 1\); \(10^3 < a \le b \le 10^6\).
• \(20\%\) số test còn lại ứng với \(20\%\) số điểm của bài không có ràng buộc gì thêm.

Trong buổi sinh hoạt ngoại khóa, thầy giáo tổ chức một trò chơi nhỏ như sau: mỗi lần thầy viết lên bảng cặp số \(a\) và \(b\), thì các bạn nhanh chóng đếm xem có bao nhiêu số nguyên trong đoạn từ \(a\) đến \(b\) có số lượng các ước của nó là một số nguyên tố.

Ví dụ, với \(a=4\) và \(b=6\), đoạn \([4, 6]\) ta có:

• Số \(4\) có \(3\) ước \((1, 2, 4)\): \(3\) là số nguyên tố;
• Số \(5\) có \(2\) ước \((1, 5)\): \(2\) là số nguyên tố;
• Số \(6\) có \(4\) ước \((1, 2, 3, 6)\): \(4\) không phải là số nguyên tố.

Nên trong đoạn \([4, 6]\) ta đếm được \(2\) số có số lượng ước của nó là số nguyên tố (\(4\) và \(5\)).

Sau \(N\) lần đưa ra các cặp số \(a\) và \(b\), thầy giáo yêu cầu đưa ra kết quả cuối cùng chính là tổng số của \(N\) lần đếm trên.

Yêu cầu: Là một học sinh đam mê lập trình trong lớp, em hãy viết một chương trình để tự động thực hiện yêu cầu của thầy giáo.

Input

Dữ liệu vào: Cho tệp văn bản CAU3.INP có cấu trúc như sau:

• Dòng 1: chứa số nguyên \(N\) là số lượng các cặp \([a, b]\) cần đếm (\(0 \leq N \leq 10^5\));
• \(N\) dòng tiếp theo: mỗi dòng chứa một cặp số nguyên \(a\) và \(b\) (\(1 \leq a \leq b \leq 10^6\)).

Các số được ghi cách nhau bởi một dấu cách.

Output

Kết quả: Ghi ra tệp văn bản CAU3.OUT gồm một dòng ghi số nguyên là tổng \(N\) lần đếm trên.

Example

2
4 6
4 7

5

Scoring

Ràng buộc:

• Có \(40\%\) số test tương ứng \(40\%\) số điểm của bài với \(1 \leq a \leq b \leq 200\) và \(N \leq 200\);
• Có \(30\%\) số test tương ứng \(30\%\) số điểm của bài với \(1 \leq a \leq b \leq 2000\) và \(N \leq 1000\);
• Có \(30\%\) số test tương ứng \(30\%\) số điểm của bài với \(1 \leq a \leq b \leq 10^6\) và \(N \leq 10^5\).