Cho xâu ~s~ gồm các kí tự in thường trong bảng chữ cái tiếng Anh. Gọi ~t_i~ là xâu nhận được từ việc xóa kí tự thứ ~i~ trong xâu ~s~.

Hãy đếm số cặp số ~(i, j)~ thỏa mãn ~i < j~ và ~t_i = t_j~.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~ (~2 \le n \le 3 \times 10^5~) — độ dài của xâu ~s~.

• Dòng tiếp theo chứa xâu ~s~ có độ dài ~n~, gồm các kí tự in thường trong bảng chữ cái tiếng Anh.

Output

• In ra một dòng duy nhất là đáp án của bài toán: số cặp số ~(i, j)~ thỏa mãn ~i < j~ và ~t_i = t_j~.

Sample Input 1

6
bccaaa

Sample Output 1

4

Notes

Ở test ví dụ trên, ta có:

• ~t_1 =~ ccaaa

• ~t_2 =~ bcaaa

• ~t_3 =~ bcaaa

• ~t_4 =~ bccaa

• ~t_5 =~ bccaa

• ~t_6 =~ bccaa

Vì vậy, có ~4~ cặp số ~(i, j)~ thỏa mãn yêu cầu đề bài là ~(2, 3)~, ~(4, 5)~, ~(4, 6)~ và ~(5, 6)~.

Cho ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~, hãy tìm số nguyên dương ~x~ nhỏ nhất thỏa mãn: ~\text{gcd}(a_i, x) > 1~ với mọi ~1 \le i \le n~.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ (~1 \le n \le 50~).

• Dòng tiếp theo chứa ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~ (~2 \le a_i \le 50~).

Output

• Một dòng duy nhất chứa đáp án của bài toán.

Sample Input 1

2
3 10

Sample Output 1

6

Sample Input 2

3
6 10 12

Sample Output 2

2

Cho một dãy ~a~ có ~n~ số ~a_1, a_2, ..., a_n~. Ta định nghĩa mức độ "vô định" của một đoạn con ~(l, r)~ là tổng xor của các giá trị xuất hiện ít nhất một lần trong đoạn ~a[l..r]~.

Yêu cầu: Cho ~q~ truy vấn, mỗi truy vấn gồm hai số ~l~ và ~r~, hãy tính độ "vô định" của dãy con ~a[l..r]~.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n,q~ (~1\le n,q \le 3\times 10^5~).

• Dòng thứ hai chứa ~n~ số nguyên ~a_1,a_2,...,a_n~ (~0\le a_i \le 10^9~) mô tả dãy số được cho.

• ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~l,r~ (~1\le l \le r \le n~) mô tả một truy vấn.

Output

• In ra ~q~ số, số thứ ~i~ là độ "vô định" của dãy con trong truy vấn thứ ~i~.

Subtask

• ~25\%~ số test thoả mãn ~n \le 5000~.

• ~75\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

7 5
1 2 1 3 3 2 3
4 7
4 5
1 7
1 3
1 5

Sample Output 1

1 3 0 3 0

Notes

Ở truy vấn thứ nhất, ta cần tính mức độ "vô định" của đoạn ~[3, 3, 2, 3]~. Đoạn con này có các giá trị ~2~ và ~3~ xuất hiện ít nhất một lần, vì thế độ "vô định" của đoạn con này là ~2\ \oplus 3 = 1~.

Ở truy vấn thứ hai, ta cần tính mức độ "vô định" của đoạn ~[3, 3]~. Đoạn con này chỉ có giá trị ~3~ xuất hiện ít nhất một lần, vì thế độ "vô định" của đoạn con này là ~3~.

Ở truy vấn thứ ba, ta cần tính mức độ "vô định" của đoạn ~[1, 2, 1, 3, 3, 2, 3]~. Đoạn con này có các giá trị ~1~, ~2~ và ~3~ xuất hiện ít nhất một lần, vì thế độ "vô định" của đoạn con này là ~1\ \oplus 2 \oplus 3 = 0~.

~2048~ là một trò chơi đơn giản nhưng vô cùng cuốn hút và cũng không kém phần thử thách. Nhiều game thủ đã dành nhiều giờ hay thậm chí là nhiều ngày chỉ để hoàn thành trò chơi này một lần.

DeMen100ns có một số nguyên dương ~n~. Tuy nhiên một số vị trí trong số ~n~ đã biến mất và được thay bằng ký tự "~?~".

DeMen100ns muốn biết có bao nhiêu cách điền các chữ số vào tất cả các ký tự "~?~" để ~n~ chia hết cho ~2048~? Vì DeMen100ns đang bận hoàn thành trò chơi ~2048~, hãy giúp cậu ấy trả lời câu hỏi trên.

Input

• Một dòng duy nhất là xâu ký tự biểu diễn số ~n~ (~1 \le n \le 10^{10^5}~). Mỗi ký tự trong xâu là một chữ số hoặc một dấu "~?~", ký tự đầu tiên luôn là một chữ số khác ~0~.

Output

• In ra trên một dòng duy nhất: số cách thay thế các dấu "~?~" bằng các chữ số sao cho ~n~ chia hết cho ~2048~. Vì kết quả có thể rất lớn, in phần dư khi lấy kết quả chia cho ~10^9 + 9~

Subtask

• ~20\%~ số test thoả mãn: số dấu "~?~" không quá ~5~.

• ~30\%~ số test khác thoả mãn: số dấu "~?~" không quá ~100~.

• ~50\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

2???

Sample Output 1

1

Note

Ở test ví dụ trên, chỉ có một cách điền duy nhất là ~2048~.

Cho đoạn mã C++ sau đây:

int random(int L, int R) {
    // return a random value in range [L, R] with an equal probability
}

int call(int l, int r) {
    if (r - l <= 1) return 0;
    int idx = random(l, r);
    if (idx == l || idx == r) return 1 + call(l, r);
    return 1 + call(l, idx - 1) + call(idx + 1, r);
}

Hãy tính Giá trị kì vọng của hàm call(1, n), với ~n~ là dữ liệu nhập vào.

Input

• Một dòng duy nhất chứa số nguyên dương ~n~ (~1 \le n \le 10^6~).

Output

• Biết đáp án của bài toán sẽ có dạng phân số tối giản ~\frac{p}{q}~, hãy in ra ~p \times q^{-1} \mod 10^9 + 7~.

Scoring

• ~40\%~ số test thỏa mãn ~n \le 500~.

• ~40\%~ số test khác thỏa mãn ~n \le 5000~.

• ~20\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

3

Sample Output 1

3

Cho tập hợp ~S~ gồm các số nguyên dương đôi một khác nhau. Gọi ~f(S)~ là số cặp số nguyên dương ~(x, y)~ thỏa ~x \le y,\ \text{gcd}(x, y) = 1~ và ~\text{lcm}(x, y) \in S~.

Ví dụ: nếu ~S = \left \{ 1, 3 \right \}~ thì các cặp số thỏa mãn là ~(1, 1)~ và ~(1, 3)~, vì vậy ~f(S) = 2~.

Cho ~q~ truy vấn, mỗi truy vấn gồm ~3~ số ~(n, l, r)~, hãy đếm số tập hợp ~S~ khác nhau thỏa mãn:

• ~f(S) = n~

• Các phần tử thuộc tập hợp ~S~ nằm trong đoạn ~[l, r]~

• Số phần tử của tập hợp ~S~ là nhỏ nhất.

Hai tập hợp ~A~ và ~B~ được xem là khác nhau, nếu tồn tại một phần tử thuộc tập ~A~ mà không thuộc tập ~B~ và ngược lại.

Input

Dòng đầu tiên chứa số nguyên dương ~q~ (~1 \le q \le 10^6~) — số truy vấn của bài toán.

~q~ dòng tiếp theo, dòng thứ ~i~ chứa ~3~ số nguyên dương ~n, l, r~ (~1 \le n \le 10^9~, ~1 \le l \le r \le 10^6~).

Output

In ra ~q~ dòng, dòng thứ ~i~ là đáp án của truy vấn tương ứng. Vì kết quả có thể rất lớn, hãy in phần dư khi lấy kết quả chia cho ~10^9 + 7~.

Sample Input 1

2
3 1 4
2 1 3

Sample Output 1

4
3

Notes

Ở truy vấn thứ nhất, các tập số thỏa mãn đề bài là ~\left \{ 1, 2, 3 \right \}~, ~\left \{ 1, 2, 4 \right \}~, ~\left \{ 1, 3, 4 \right \}~, ~\left \{ 2, 3, 4 \right \}~.

Ở truy vấn thứ nhất, các tập số thỏa mãn đề bài là ~\left \{ 1, 2 \right \}~, ~\left \{ 1, 3 \right \}~, ~\left \{ 2, 3 \right \}~.