Trại hè Sáng tạo bảng B, Buổi 1

Một trung tâm dữ liệu đang vận hành \(n\) cụm máy chủ để xử lý tính toán hiệu năng cao. Nhằm tối ưu hóa năng lực tính toán, hệ thống được thiết kế theo kiến trúc phân tầng vô cùng đặc biệt. Cụ thể, tại cụm máy chủ thứ \(i\) (\(1 \le i \le n\)), kiến trúc được tổ chức chặt chẽ thành ba tầng như sau:

• Tầng 1: Vận hành đúng \(i\) máy chủ điều phối trung tâm.
• Tầng 2: Mỗi máy chủ điều phối chịu trách nhiệm quản lý trực tiếp \(i\) máy trạm.
• Tầng 3: Mỗi máy trạm được cấp phát đúng \(i\) luồng xử lý độc lập để thực thi tác vụ.

Yêu cầu: Cho biết số lượng cụm máy chủ \(n\). Hãy tính tổng số lượng luồng xử lý độc lập được thiết lập trong toàn bộ trung tâm dữ liệu (gồm cả \(n\) cụm). Vì kết quả có thể rất lớn, chỉ cần in ra phần dư của tổng này khi chia cho \(10^9 + 7\).

Input

• Dòng duy nhất gồm một số nguyên dương \(n\).

Output

• Dòng duy nhất chứa một số nguyên là kết quả của bài toán (tổng số luồng xử lý sau khi modulo cho \(10^9 + 7\)).

Example

3

36

Ràng buộc

• Subtask 1 (\(30\%\) số điểm): \(n \le 100\).
• Subtask 2 (\(30\%\) số điểm): \(n \le 10^6\).
• Subtask 3 (\(40\%\) số điểm): \(n \le 10^{12}\).

Tại trung tâm nghiên cứu vô tuyến, các chuyên gia đang thử nghiệm một giao thức truyền tin mật mã mới. Mỗi thông điệp được mã hóa thành một chuỗi gồm \(n\) tín hiệu rời rạc, tín hiệu thứ \(j\) có cường độ là một số nguyên dương \(a_j\).

Để giải mã được thông điệp, hệ thống cần tìm cách đồng bộ hóa chuỗi tín hiệu này. Quá trình đồng bộ hóa thành công nếu hệ thống có thể đảo lộn thứ tự các tín hiệu trong chuỗi ban đầu để tạo ra một cấu hình mới, sao cho tồn tại một điểm cắt \(i\) (\(1 \le i < n\)) chia chuỗi thành hai phần thỏa mãn tính chất:

• Ngưỡng năng lượng tối thiểu của phần đầu tiên (từ vị trí \(1\) đến \(i\)) phải bằng chính xác tần số cơ bản (ước chung lớn nhất) của phần thứ hai (từ vị trí \(i + 1\) đến \(n\)).

Nói cách khác, từ dãy \(a_1, a_2, \dots, a_n\) ban đầu, cần kiểm tra xem có tồn tại một hoán vị của dãy và một chỉ số \(i\) sao cho:

Yêu cầu: Cho trước \(T\) bộ dữ liệu thử nghiệm, mỗi bộ chứa \(n\) cường độ tín hiệu \(a_1, a_2, \dots, a_n\). Với mỗi bộ dữ liệu, hãy xác định xem có tồn tại cách đảo lộn thứ tự thỏa mãn điều kiện đồng bộ khóa hay không.

Input

• Dòng đầu tiên chứa số nguyên dương \(T\) (\(T \le 5\)) là số lượng bộ test.
• Tiếp theo là \(T\) nhóm dòng, mỗi nhóm tương ứng với một bộ test có cấu trúc như sau:
  • Dòng thứ nhất chứa số nguyên dương \(n\) là số lượng tín hiệu.
  • Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) (\(a_j \le 10^{12}\)), các số được ghi cách nhau bởi khoảng trắng.

Output

• Gồm \(T\) dòng, dòng thứ \(k\) ghi đáp án cho bộ test thứ \(k\). In ra YES nếu tồn tại cách hoán vị thỏa mãn yêu cầu, ngược lại in ra NO.

Example

2
3
6 4 2
3
3 5 7

YES
NO

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \le 10\).
• Subtask \(2\) (\(30\%\) số điểm): \(10 < n \le 100\).
• Subtask \(3\) (\(40\%\) số điểm): \(100 < n \le 10^6\) (Tổng \(n\) trong tất cả các testcase không vượt quá \(10^6\)).

Để đối phó với tình trạng biến đổi khí hậu đang ảnh hưởng trực tiếp đến mùa màng và đời sống dân sinh, một trạm quan trắc môi trường đã tiến hành thu thập dữ liệu nhiệt độ trung bình hàng ngày trong suốt một khoảng thời gian dài. Trong \(n\) ngày liên tiếp, nhiệt độ đo được ghi nhận lại thành một chuỗi số nguyên \(a_1, a_2, \dots, a_n\).

Các chuyên gia khí tượng định nghĩa trọng số chênh lệch nhiệt độ của một giai đoạn kéo dài từ ngày thứ \(i\) đến ngày thứ \(j\) (\(1 \leq i \leq j \leq n\)) là \(F(i, j) = \max(a_i, a_{i+1}, \dots, a_j) - \min(a_i, a_{i+1}, \dots, a_j)\). Một giai đoạn được đánh giá là có “biến động thời tiết khắc nghiệt” nếu chênh lệch giữa nhiệt độ cao nhất và thấp nhất trong giai đoạn đó vượt qua hoặc bằng một ngưỡng rủi ro \(K\) cho trước.

Yêu cầu: Cho biết ngưỡng rủi ro \(K\) và chuỗi dữ liệu nhiệt độ \(n\) ngày. Hãy đếm xem có bao nhiêu giai đoạn \((i, j)\) (\(i \leq j\)) được xếp loại là có biến động thời tiết khắc nghiệt (tức là \(F(i, j) \ge K\)).

Input

• Dòng đầu tiên gồm hai số nguyên dương \(n\) và \(K\) (\(K \le 10^9\)), phân tách nhau bởi khoảng trắng.
• Dòng thứ hai gồm \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(|a_i| \le 10^9\)) thể hiện nhiệt độ của các ngày. Các số được ghi cách nhau bởi khoảng trắng.

Output

• Dòng duy nhất chứa một số nguyên là số lượng các giai đoạn (cặp chỉ số \((i, j)\)) thỏa mãn điều kiện có mức biến động nhiệt độ \(F(i, j) \ge K\).

Example

4 2
1 3 2 4

5

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \le 100\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \le 1000\).
• Subtask \(3\) (\(40\%\) số điểm): \(n \le 10^5\).

Trong ngày hội STEM của trường, câu lạc bộ Tin học tổ chức một cuộc thi lập trình điều khiển robot di chuyển trên sa bàn. Sa bàn là một mặt phẳng được chia thành lưới ô vuông kích thước \(M \times N\) (gồm \(M\) dòng và \(N\) cột). Trên sa bàn, mỗi ô vuông có thể là một khu vực di chuyển an toàn (kí hiệu là số 0) hoặc một khu vực có chướng ngại vật (kí hiệu là số 1).

Để kiểm tra độ linh hoạt của thuật toán định vị, ban tổ chức đưa ra một thử thách: robot phải thực hiện một "hành trình đơn" đi qua đúng \(K\) ô an toàn. Một hành trình hợp lệ được định nghĩa như sau:

• Xuất phát từ một ô an toàn bất kỳ trên sa bàn.
• Ở mỗi bước, robot chỉ được phép di chuyển sang một ô an toàn kề cạnh (chung một cạnh) với ô hiện tại.
• Robot tuyệt đối không được phép đi vào khu vực chướng ngại vật và không được phép lặp lại (đi lại vào) bất kỳ ô nào đã từng ghé thăm trước đó trong cùng một hành trình.
• Tổng số ô an toàn mà robot đặt chân đến (tính cả ô xuất phát) phải bằng chính xác \(K\).

Yêu cầu: Cho trước kích thước \(M\), \(N\), độ dài hành trình \(K\) và bản đồ sa bàn. Hãy tính tổng số lượng hành trình đơn hợp lệ khác nhau mà robot có thể thực hiện. Hai hành trình được coi là khác nhau nếu dãy tọa độ các ô mà robot lần lượt đi qua là khác nhau.

Input

• Dòng đầu tiên gồm ba số nguyên dương \(M\), \(N\), \(K\) (\(M, N \leq 10\)).
• \(M\) dòng tiếp theo, mỗi dòng gồm \(N\) số nguyên có giá trị 0 hoặc 1, biểu diễn bản đồ sa bàn (0 là ô trống, 1 là chướng ngại vật). Các số được ghi cách nhau bởi một khoảng trắng.

Output

• Dòng duy nhất chứa một số nguyên là tổng số lượng hành trình đơn hợp lệ độ dài \(K\) đếm được.

Example

2 2 3
0 0
0 1

2

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(K = 4\).
• Subtask \(2\) (\(20\%\) số điểm): \(K = 8\).
• Subtask \(3\) (\(60\%\) số điểm): \(K = 10\).

Trong lúc chờ Tân loại bỏ bớt các hình dạng không hợp lý cho trò chơi oẳn tù tì, Lương và Định viết ra một con số đặc biệt: \(2941999\). Sau đó, hai bạn đã rủ Ngọc cùng ngồi giết thời gian bằng một trò chơi thú vị, ba bạn cùng cộng bình phương các chữ số của con số đặc biệt lại và lấy kết quả đó thay thế cho con số hiện tại: \(2^2+9^2+4^2+1^2+9^2+9^2+9^2=4+81+16+1+81+81+81=345\). Họ kiên trì lặp lại bước trên: \(345→50→25→29→85→89→145→42…\) cho tới khi nào được kết quả là số \(1\) thì dừng lại, vì cả ba đều rất ghét con số này (gợi lên sự lẻ loi của những chàng trai FA). Với tài năng toán học thiên bẩm, Ngọc nhận ra rằng nếu xuất phát từ con số \(2941999\) như trên thì không bao giờ biến đổi được nó về số \(1\) bằng cách lặp đi lặp lại bước cộng bình phương các chữ số. Lương và Định cũng công nhận điều này và hai bạn nhờ Ngọc xác định giúp xem có bao nhiêu con số đặc biệt như vậy (không thể biến đổi về số 1) trong đoạn các số tự nhiên từ \(L\) đến \(R\).

Yêu cầu: Với từng cặp số tự nhiên \(L\) và \(R (1≤L≤R≤10^{18})\), hãy giúp Ngọc xác định số lượng số đặc biệt nằm trong đoạn \([L,R]\).

Input

• Dòng đầu chứa số nguyên dương \(T\) là số lượng câu hỏi của Lương và Định.
• Tiếp đến là \(T\) dòng, mỗi dòng chứa hai số tự nhiên \(L\) và \(R\) biểu thị câu hỏi tương ứng.

Output

Ghi ra \(T\) dòng, mỗi dòng chứa một số nguyên duy nhất là câu trả lời cho câu hỏi tương ứng.

Scoring

• Subtask 1 (\(20\%\) số điểm): \(T \le 30\) và \(R-L \le 10^6\).
• Subtask 2 (\(20\%\) số điểm): \(T \le 100\) và \(1 \le L \le R \le 10^9\).
• Subtask 3 (\(60\%\) số điểm): \(T \le 100\)

Example

1
2941999 2942002

3