*Nguồn đề + test: * Free Contest (https://freecontest.net/),

* Đề gốc: * https://drive.google.com/file/d/181C1ZLuJW-n0Ln4Y221uAbShnJOAnLIB/view

*Lời giải: * https://drive.google.com/file/d/1IXafO_AxmNyrrDYVg2yeGIzvBKGKP3nh/view

Cho một mê cung gồm n phòng xếp thành 1 hàng, các phòng đánh số từ 1 đến n. Mỗi phòng được mã hóa bằng một số tự nhiên từ 0 đến ~2^{30}-1~. Hải đang ở phòng số 1. Hải có thể di chuyển từ phòng a đến phòng b khi và chỉ khi:

• a < b

• Gọi số mã hóa của phòng a và b lần lượt là x và y. Khi đó phải tồn tại số tự nhiên k để :

  ~ \left \lfloor \frac{x}{2^k} \right \rfloor \quad , \left \lfloor \frac{y}{2^k} \right \rfloor \quad ~ đều là số lẻ.

  ~ \left \lfloor x \right \rfloor \quad ~ : là số x làm tròn xuống. Vd: ~ \left \lfloor 1.6 \right \rfloor \quad ~ = 1

Đồng thời, số cách di chuyển từ phòng a *đến phòng *b bằng số lượng k thỏa mãn yêu cầu trên.

Hải biết rằng mình cần đến được phòng n để thoát khỏi mê cung. Hỏi Hải có bao nhiêu cách để di chuyển từ phòng 1 đến phòng n? Hai cách di chuyển được gọi là khác nhau nếu Hải đi qua một phòng trong một cách nhưng không đi qua trong cách kia, hoặc Hải dùng 2 cách khác nhau để di chuyển giữa hai phòng. Đáp án có thể rất lớn hãy đưa ra đáp án chia dư cho 10^9 + 7.

Input

• Dòng đầu tiên chứa N ~(1 \leq N \leq 10^5)~
• Dòng thứ hai gồm n số nguyên dương không lớn hơn ~10^9~, trong đó số thứ i là số mã hóa của phòng thứ i.

Output

• In ra một số nguyên duy nhất là số cách di chuyển từ phòng 1 đến phòng n, modulo ~10^9 +7~.

Sample Input 1

4
1 3 3 1

Sample Output 1

5

Giải thích đáp án :

Đường đi 1 :
    phòng 1 - 2 : k = 0
    phòng 2 - 3 : k = 0
    phòng 3 - 4 : k = 0

Đường đi 2 :
    phòng 1 - 2 : k = 0
    phòng 2 - 3 : k = 1
    phòng 3 - 4 : k = 0

Đường đi 3 :
    phòng 1 - 4 : k = 0

Đường đi 4 :
    phòng 1 - 2 : k = 0
    phòng 2 - 4 : k = 0

Đường đi 5 :
    phòng 1 - 3 : k = 0
    phòng 3 - 4 : k = 0

Sample Input 2

9
1 3 5 7 9 11 13 15 17

Sample Output 2

732

Task:

• Subtask 1 (10% số test) : ~n \leq 8~
• Subtask 2 (40% số test) : ~n \leq 10^3~
• Subtask 3 (50% số test) : Không ràng buộc gì thêm

*Nguồn đề + test: * Free Contest (https://freecontest.net/),

* Đề gốc: * https://drive.google.com/file/d/1N2USUPOOdO7rEyskmAhBYtLcg2fCoaDG/view

*Lời giải: * https://drive.google.com/file/d/1jEnIuv8geT9aYUwzc5CPV4CNl7RW9QRz/view

Một hiệu thuốc bán A loại khẩu trang và B loại dung dịch sát khuẩn. Hộp khẩu trang loại i ~(1 \leq i \leq A)~ có giá ~a_i~, dung dịch sát khuẩn loại j ~(1 \leq j \leq B)~ có giá ~b_j~. Để khuyến khích mọi người đeo khẩu trang và sử dụng dung dịch sát khuẩn để phòng ngừa, ngăn chặn lây lan dịch bệnh Covid-19, cửa hàng quyết định tặng M loại phiếu giảm giá cho khách hàng. Phiếu thứ i sẽ giảm ~c_i~ đồng nếu bạn mua một hộp khẩu trang loại ~x_i~ cùng với một dung dịch sát khuẩn loại ~y_i~.

Hỏi bạn cần ít nhất bao nhiêu để mua một hộp khẩu trang và một dung dịch sát khuẩn. Biết rằng mỗi phiếu giảm giá chỉ sử dụng một lần.

Input

• Dòng đầu tiên gồm ba số nguyên A, B, M ~(1 \leq A, B, M \leq 10^5)~
• Dòng thứ hai gồm A số nguyên ~a_i~ ~(1 \leq a_i \leq 10^5)~ là giá của hộp khẩu trang loại i.
• Dòng thứ ba gồm B số nguyên ~b_j~ ~(1 \leq b_j \leq 10^5)~ là giá của dung dịch sát khuẩn loại i.
• M dòng tiếp theo, dòng thứ i gồm 3 số nguyên ~x_i, y_i, c_i~ ~(1 \leq x_i \leq A, 1 \leq y_i \leq B, c_i \leq a_{x_i}+b_{y_i} )~

Output

• Gồm 1 dòng duy nhất là kết quả bài toán.

Sample Input 1

2 3 1
3 3
3 3 3
1 2 1

Sample Output 1

5

Sample Input 2

1 1 2
10
10
1 1 5
1 1 10

Sample Output 2

10

*Nguồn đề + test: * Free Contest (https://freecontest.net/),

* Đề gốc: * https://drive.google.com/file/d/14jGaBgQ77dVgKT3jZwUgyxmMBniIJZu-/view

*Lời giải: * https://drive.google.com/file/d/1pTVSSpee2tyMRrSphdLOJGVhVPysCqKV/view

Hải chọn ra N số nguyên liên tiếp trong khoảng từ 1 đến 100. Sau đó Hải đố bạn biết tổng các số mà Hải đã chọn là chẵn hay lẻ. Hãy viết chương trình để trả lời câu đố của Hải. Nếu tổng chắc chắn là một số chẵn in ra "0", nếu tổng chắc chắn là số lẻ in ra "1", nếu tổng có thể là số chẵn hoặc lẻ in ra "2".

Input

• Dòng đầu tiên gồm một số nguyên N ~(1 \leq N \leq 100)~

Output

• In ra kết quả của bài toán.

Sample Input 1

1

Sample Output 1

2

Sample Input 2

2

Sample Output 2

1

*Nguồn đề + test: * Free Contest (https://freecontest.net/),

* Đề gốc: * https://drive.google.com/file/d/15y5cnDohfBpU4AOM1QgwDZJnui_YPp6z/view

*Lời giải: * https://drive.google.com/file/d/161OduQZ7Pnaa6kjBuAZ-2xcn5hCsaYhE/view

Một dãy X độ dài x được gọi là dãy số phan xi păng nếu ~\forall{i}, 2 \leq i \leq x : X_{i-1} < X_{i}.~

Cho một dãy A có độ dài n. Một tập hợp B có b phần tử có giá trị nằm trong đoạn [1,n] được gọi là tập hợp phan xi păng nếu có thể thay đổi vị trí các phần tử của dãy sau ~A_{B_1}, A_{B_2}, A_{B_3},..., A_{B_b}~ sao cho dãy này trở thành dãy phan xi păng.

Tức là đếm số tập hợp B: gồm ~ 1 \leq b_i \leq n ~, sao cho từ tập hợp b ta có một dãy(là tập con của A) tương ứng ~A_{b_1}, A_{b_2}, A_{b_3},...~ thỏa mãn sao cho tồn tại 1 cách sắp xếp dãy này thành một dãy phan xi păng.

Vd dãy :

• A : 3 1 2 3 2

• Tập B có thể là {1,2} => A[1] = 3 , A[2] = 1 => ta có dãy 3,1 sắp xếp lại ta có dãy 1,3 là dãy phan xi păng

• Lưu ý {1,2} = {2,1} "tập hợp"

Hãy đếm số tập hợp B là tập hợp phan xi păng.

Input

• Dòng đầu tiên gồm một số nguyên N ~(1 \leq N \leq 10^5)~.
• Dòng tiếp theo chứa n số nguyên ~A_i~.

Output

• Kết quả bài toán, chia dư cho ~10^9 + 7~.

Sample Input 1

5
3 1 2 3 2

Sample Output 1

18

Giải thích

Các tập hợp thỏa mãn đó là {}, {1}, {2}, {3}, {4}, {5}, {1,2}, {1,3}, {1,5}, {2,3}, {2,4}, {2,5}, {3,4}, {4,5}, {1,2,3}, {1,2,5}, {2,3,4}, {2,4,5}.

Task:

• Subtask 1 (60% số điểm) : ~n \leq 20~
• Subtask 2 (40% số điểm) : ~n \leq 2 . 10^5~

*Nguồn đề + test: * Free Contest (https://freecontest.net/),

* Đề gốc: * https://drive.google.com/file/d/14mUwz9rvb78k4IL-GTDSkNR7PSbS4xPq/view

*Lời giải: * https://drive.google.com/file/d/1ACRIlL6TB5QrfL3eMzycZG9Ww33kVKcY/view

Cân bằng của một mảng được định nghĩa là số cặp chỉ số (i,j) (i < j) với giá trị bằng nhau ~(a_i = a_j)~. Ví dụ cân bằng của mảng a = [1,1,2,2,1] là 4. Số cặp chỉ số với giá trị bằng nhau là (1,2), (1,5), (2,5) và (3,4).

Cho một mảng a có n phần tử, in ra tổng cân bằng của tất cả các mảng con của a.

Một mảng b được định nghĩa là mảng con của mảng a nếu ta có thể thu được mảng b sau khi xóa một vài phần tử (có thể là không hoặc tất cả phần tử) ở đầu và cuối của mảng a.

Input

• Dòng đầu tiên gồm một số nguyên T số test ~(1 \leq T \leq 100)~
• Dòng đầu tiên của mỗi test chứa số n ~(1 \leq n \leq 10^{4} )~
• Dòng thứ hai chứa n số lần lượt là phần tử trong mảng a : ~a_1, a_2, a_3, ... , a_n (1 \leq a_i \leq 10^9)~

Output

• Với mỗi test, in ra một số là tổng cân bằng của tất cả mảng con của a

Sample Input 1

2 
4
1 2 1 1
4
1 2 3 4

Sample Output 1

6
0

Giải thích

• Test 1 : [1,2] cân bằng là 0, [1,1] cân bằng là 1, [1,2,1] cân bằng là 1, [2,1,1] cân bằng là 1, [1,2,1,1] cân bằng là 3. Đáp án là 6.