Quốc tế thiếu nhi 2020

Flow God có \(n\) em gái. Sau khi cùng các em làm việc nhà trong ngày sinh nhật của mình, Flow God và các em gái được bố mẹ thưởng kẹo. Mức thưởng được xét dựa trên năng lực: Làm ít ăn ít, làm nhiều ăn nhiều. Em gái thứ \(i\) được thưởng \(a_i\) viên kẹo, còn Flow God được thưởng \(x\) viên kẹo.

Flow God rất rộng lượng nhưng các em gái thì không. Nói cách khác, Flow God có thể đem kẹo của mình cho các em nhưng các em gái thì chỉ nhận kẹo mà không bao giờ chia sẻ cho ai khác. Là một người con trung thành với lý tưởng Xã Hội Chủ Nghĩa, Flow God muốn số kẹo của mọi người phải bằng nhau. Để thực hiện điều đó, anh có thể lấy vài viên kẹo của mình cho vài em gái. Flow God tự hỏi liệu mình có thể làm mọi người bình đẳng được không?

Input

• Dòng đầu tiên chứa một số nguyên dương \(t\), số trường hợp mà Flow God cần giúp đỡ (Flow God có nhiều nhóm em gái khác nhau ...)

Với mỗi trường hợp:

• Dòng đầu tiên chứa \(2\) số nguyên \(n, x\)
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, ..., a_n\)

Output

• In ra \(t\) dòng, mỗi dòng chứa đáp số cho trường hợp tương ứng. In ra "YES" nếu Flow God có thể đạt được ước nguyện làm cho thế giới bình đẳng, "NO" nếu ngược lại.

Constraints

• \(t \leq 10^5\)
• \(1 \leq n \leq 10^5, 0 \leq x \leq 10^9\)
• \(0 \leq a_i \leq 10^9\)
• Tổng các số \(n\) trong một input không vượt quá \(10^5\)

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(a_1=a_2=...=a_n=0\).
• Subtask \(2\) (\(30\%\) số điểm): \(a_1=a_2=...=a_n\).
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

3
3 5
0 1 2
2 4
3 3
4 0
0 0 0 0 

YES
NO
YES

Nhân ngày quốc tế thiếu nhi, ami đã tặng em gái của Flow God xấu-trai-hơn-ami một chiếc máy thần kì. Trên chiếc máy là 2 nút màu tím và hồng, cùng 2 số \(H\) và \(I\). Nếu ấn nút màu tím, số \(H\) sẽ tăng 1 đơn vị, nếu ấn nút màu hồng, số \(I\) sẽ tăng 1 đơn vị. Flow God ghen tuông vì ami đã tặng cho em gái cưng của mình một món quà cool ngầu như thế, bèn tìm ra cách để ami phải mất mặt.

Flow God xấu-trai-hơn-ami muốn ami ấn các nút tím và hồng tổng cộng không quá F lần. Sau khi thực hiện các thao tác, giả sử 2 số mà ami nhận được là \(N\) và \(R\), Flow God muốn \(gcd(N,R)\) là lớn nhất có thể. Nhắc lại, \(gcd(a,b)\) là một số \(c\) lớn nhất mà cả \(a\) và \(b\) đều chia hết cho \(c\) (quy ước \(gcd(0, n)=gcd(n, 0)=n\) với mọi số nguyên dương \(n\)). Tuy nhiên, ami quá thần thánh, đã tìm ra kết quả siêu nhanh. Flow God tức tối, giận cuom1999 chém ma. "ma" ở đây chính là các bạn tham gia contest.

Các bạn cần trả lời \(q\) câu hỏi của Flow God, mỗi câu hỏi có dạng \(H\) \(I\) \(F\). Cần in ra \(gcd(N,R)\) lớn nhất, \(N\) và \(R\) là các số nhận được, sau khi ấn hai nút tím và hồng không quá \(F\) lần.

Input

• Dòng đầu tiên chứa một số nguyên dương \(q\) là số câu hỏi của Flow God xấu-trai-hơn-ami.
• Tiếp theo là \(q\) dòng, mỗi dòng chứa một bộ số nguyên không âm \(H\) \(I\) \(F\) là một câu hỏi.

Output

• In ra \(q\) dòng, mỗi dòng là một số nguyên là \(gcd(N,R)\) lớn nhất có thể đạt được.

Dữ liệu đảm bảo luôn có kết quả.

Constraints

• \(H, I \leq 10^5\)
• \(q \leq 10^2\)
• \(F \leq 10^{13}\)

Scoring

• Subtask \(1\) (\(5\%\) số điểm): \(H = 0, I \leq 10^5, F \leq 10^{13}, q \leq 10^2\).
• Subtask \(2\) (\(20\%\) số điểm): \(H, I \leq 10^5, q \leq 10^2, F \leq 10^{5}\).
• Subtask \(3\) (\(10\%\) số điểm): \(H, I \leq 10^5, q \leq 10^2, F = 0\)
• Subtask \(4\) (\(65\%\) số điểm): \(H, I \leq 10^5, q \leq 10^2, F \leq 10^{13}\)

Example

3
0 1 1
1 1 2
2 4 1

2
2
2

dungde99 vừa vẽ ra một bảng số nguyên dương gồm \(M\) hàng và \(N\) cột, các hàng được đánh số từ \(1\) đến \(M\) từ trên xuống và các cột được đánh số từ \(1\) đến \(N\) từ trái sang phải. dungde99 ký hiệu ô \((i, j)\) là ô nằm ở giao điểm của hàng \(i\) và cột \(j\) của bảng. Sau đó, dungde99 đưa ra bộ bốn số \(x_1\), \(y_1\), \(x_2\) và \(y_2\) rồi đố Flow God tìm một đường đi tối ưu từ ô \(\left(x_1, y_1\right)\) đến ô \(\left(x_2, y_2\right)\), tức là một đường đi xuất phát tại ô \(\left(x_1, y_1\right)\) mà tại mỗi bước Flow God chỉ có thể di chuyển sang ô kề bên phải hoặc ô kề bên dưới của ô hiện tại, đồng thời tổng các số ghi ở các ô trên đường đi (bao gồm cả ô \(\left(x_2, y_2\right)\)) phải nhỏ nhất có thể. Flow God nhanh chóng trả lời được câu đố đầu tiên của dungde99 nhưng sau đó dungde99 lại hỏi tiếp hàng loạt câu hỏi dạng tương tự như vậy khiến Flow God phải bó tay trong sự lúng túng. Các bạn hãy giúp Flow God giải đáp tất cả các câu đố này nhé!

Input

• Dòng đầu tiên chứa một số nguyên \(x\).
• Dòng tiếp theo chứa một số nguyên \(n\).

Output

• Một dòng duy nhất chứa một nguyên là \(x ^ n\) sau khi chia lấy dư cho \(10 ^ 9 + 7\).

Constraints

• \(1 \leq x \leq 10 ^ 9\)
• \(1 \leq n \leq 10 ^ 9\)

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \leq 10 ^ 6\).
• Subtask \(2\) (\(70\%\) số điểm): Không có ràng buộc gì thêm.

Example

3
2 

9

4
5 

1024

Cho hai số nguyên dương \(n, k\). Đếm xem có bao nhiêu hoán vị \(p_{1}, p_{2}, \ldots, p_{n}\) của \(1, 2, \ldots, n\) thỏa mãn \(p_{i} > p_{i / k}\) với mọi \(1 \leq i \leq n\).

Trong đó, \(a / b\) là số nguyên lớn nhất không vượt quá \(\dfrac{a}{b}\) và quy ước \(p_{0} = 0\).

Input

• Gồm hai số nguyên dương \(n, k\) \((1 \leq n, k \leq 10^{6})\).

Output

• In ra số lượng hoán vị thỏa mãn điều kiện sau khi \(\mod (10^{9} + 7)\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 10\).
• Subtask \(2\) (\(10\%\) số điểm): \(k > n\).
• Subtask \(3\) (\(10\%\) số điểm): \(k = n\).
• Subtask \(4\) (\(20\%\) số điểm): \(k > \dfrac{n}{2}\).
• Subtask \(5\) (\(20\%\) số điểm): \(n, k \leq 10^{3}\).
• Subtask \(6\) (\(20\%\) số điểm): \(n, k \leq 10^{6}\).

Example

3 2 

2

8 3 

2520