Chọn HSG tỉnh THPT Gia Lai 2025-2026

Trong lý thuyết số học, bên cạnh việc nghiên cứu từng số riêng lẻ, việc khảo sát cấu trúc của cả một dãy số cũng mang lại nhiều điều thú vị.

Đặc biệt, mối liên hệ giữa các phần tử thông qua ước chung lớn nhất phản ánh mức độ liên kết về mặt số học giữa chúng.

Một dãy số nguyên dương được gọi là liên kết nếu ước chung lớn nhất của toàn bộ dãy bằng 1.

Mức độ liên kết của một dãy chính là tổng các phần tử trong dãy.

Ví dụ, dãy [1, 1, 1, 1] là một dãy liên kết có mức độ liên kết bằng 4, vì:

• Ước chung lớn nhất của dãy là 1.
• Tổng các phần tử là 4.

Cho một số nguyên dương \(S\), hãy đếm có bao nhiêu dãy số nguyên dương có cùng mức độ liên kết là \(S\).

Hai dãy được xem là khác nhau nếu số lượng phần tử khác nhau hoặc tồn tại một vị trí mà hai dãy có giá trị khác nhau.

Yêu cầu

Với mỗi test, cho một số nguyên dương \(S\).
Hãy đếm số dãy số nguyên dương có tổng bằng \(S\) và có ước chung lớn nhất bằng \(1\).

Vì kết quả có thể rất lớn, hãy in ra số dư của kết quả khi chia cho \(10^9 + 7\).

Input

• Dòng đầu tiên chứa số nguyên dương \(t\) (\(1 \le t \le 100\)), là số lượng test.
• \(t\) dòng tiếp theo, mỗi dòng chứa một số nguyên dương \(S\) (\(1 \le S \le 10^9\)).

Output

• In ra \(t\) dòng.
• Dòng thứ \(i\) là đáp án của test thứ \(i\), lấy dư theo modulo \(10^9 + 7\).

Example

3 
4 
5 
1

6 
15 
1

Scoring

• Subtask 1 (\(30\%\) số điểm): \(1 \le S \le 20\).
• Subtask 2 (\(30\%\) số điểm): \(1 \le S \le 10^6\).
• Subtask 3 (\(40\%\) số điểm): \(1 \le S \le 10^9\).

Một xâu được gọi là xâu đối xứng nếu đọc từ trái sang phải hay đọc từ phải sang trái đều giống nhau.

Cho một xâu S có độ dài N, chỉ gồm các ký tự chữ cái in thường từ a đến z.

Có Q truy vấn, mỗi truy vấn gồm hai số nguyên L và R.

Với mỗi truy vấn, hãy đếm số lượng cặp (X, Y) thỏa mãn:

\(L \le X \le Y \le R.\)
Xâu con từ vị trí X đến vị trí Y của xâu S là một xâu đối xứng.

Nói cách khác, với mỗi đoạn [L, R], hãy đếm số lượng xâu con đối xứng nằm hoàn toàn trong đoạn đó.

Yêu cầu

Với mỗi truy vấn [L, R], hãy in ra số lượng xâu con đối xứng của xâu S nằm trong đoạn từ L đến R.

Input

• Dòng đầu tiên chứa xâu S có độ dài N (\(1 \le N \le 5000\)), chỉ gồm các chữ cái in thường.
• Dòng thứ hai chứa số nguyên Q (\(1 \le Q \le 10^5\)).
• Q dòng tiếp theo, mỗi dòng chứa hai số nguyên L và R (\(1 \le L \le R \le N\)).

Output

• In ra Q dòng.
• Dòng thứ i là số lượng xâu con đối xứng nằm hoàn toàn trong đoạn tương ứng với truy vấn thứ i.

Example

caaaba 
5 
1 1 
1 4
2 3
4 6 
4 5

1 
7
3
4 
2

Scoring

• Subtask 1 (\(20\%\) số điểm): \(N, Q \le 100\).
• Subtask 2 (\(40\%\) số điểm): \(N, Q \le 300\).
• Subtask 3 (\(20\%\) số điểm): \(N, Q \le 2000\).
• Subtask 4 (\(20\%\) số điểm): Không có ràng buộc nào thêm.

Ban tổ chức chuẩn bị \(m\) loại quà, số lượng mỗi loại là không hạn chế.

Loại quà thứ \(i\) có hai tham số tính điểm là \(a_i\) và \(b_i\).

Nếu chọn loại quà thứ \(i\) lần đầu tiên, số điểm nhận được là \(a_i\).

Nếu tiếp tục chọn loại quà đó thêm các lần sau, mỗi lần chọn thêm sẽ được cộng \(b_i\) điểm.

Nói cách khác, nếu chọn loại quà thứ \(i\) đúng \(k\) lần thì số điểm nhận được là:

với \(k \ge 1\).

Người chơi được phép chọn đúng \(n\) món quà từ \(m\) loại quà đã chuẩn bị.

Yêu cầu

Hãy tính tổng điểm lớn nhất có thể đạt được khi chọn đúng \(n\) món quà.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) (\(1 \le n \le 10^9\), \(1 \le m \le 10^5\)).
• \(m\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(a_i\) và \(b_i\) (\(0 \le a_i, b_i \le 10^9\)).

Output

• In ra một số nguyên duy nhất là tổng điểm lớn nhất có thể đạt được.

Example

3 3 
7 1 
2 5 
5 0

14

5 3 
5 2 
4 2 
3 1

16

Ngày nay, việc sử dụng các phần mềm ứng dụng trở nên rất phổ biến. Người dùng thường có xu hướng sử dụng tiếp các ứng dụng có liên quan với ứng dụng mà họ vừa dùng.

Một công ty cung cấp ứng dụng trực tuyến đang theo dõi \(N\) ứng dụng, được đánh số từ \(1\) đến \(N\).

Ứng dụng thứ \(i\) hiện có số lượt tải là \(a_i\).

Ban đầu, chưa có thông tin nào về việc hai ứng dụng có liên quan với nhau.

Có \(Q\) truy vấn thuộc hai loại:

• 1 u v: ghi nhận rằng có người dùng đã tải cả ứng dụng \(u\) và ứng dụng \(v\). Khi đó, hai ứng dụng này được xem là có liên quan. Nếu ứng dụng \(x\) liên quan với \(y\), và \(y\) liên quan với \(z\), thì \(x\) cũng được xem là liên quan với \(z\).
• 2 u c: hỏi có bao nhiêu ứng dụng có đúng \(c\) lượt tải và liên quan với ứng dụng \(u\).

Nói cách khác, với truy vấn loại 2 u c, cần đếm số ứng dụng nằm trong cùng nhóm liên quan với \(u\) và có giá trị lượt tải bằng \(c\).

Yêu cầu

Hãy thực hiện \(Q\) truy vấn và in kết quả cho mỗi truy vấn loại \(2\).

Input

• Dòng đầu tiên chứa hai số nguyên dương \(N\) và \(Q\) (\(1 \le N \le 10^5, 1 \le Q \le 2 \cdot 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên dương \(a_1, a_2, \dots, a_N\) (\(1 \le a_i \le N\)).
• \(Q\) dòng tiếp theo, mỗi dòng là một trong hai dạng:
  • 1 u v (\(1 \le u, v \le N, u \ne v\)).
  • 2 u c (\(1 \le u, c \le N\)).

Output

• Với mỗi truy vấn loại \(2\), in ra một số nguyên trên một dòng là kết quả tương ứng.

Example

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

1 
0 
3 
1