Cho một số nguyên dương $n$ và $k$ số nguyên dương $a_1,a_2,\dots,a_k ≤ 2n$ . Người ta bày sẵn $2n$ đồng xu trên bàn sao cho có đúng $n$ đồng xu ngửa và $n$ đồng xu sấp. Với mỗi thao tác, bạn có thể chọn một số bất kỳ trong tập $a$, giả sử số bạn chọn là $t$. Bạn sẽ lấy các đồng xu liên tiếp (có thể không lấy đồng xu nào) có cùng trạng thái (cùng sấp hoặc cùng ngửa), sau đó chuyển chúng ra đầu dãy. Ví dụ:
Với trạng thái các đồng xu được đặt như sau: AABBBBAA (ký hiệu A là mặt ngửa và B là mặt sấp) và $t = 4$, ta có thể thu được các trạng thái sau:

• BBBAABAA (chuyển các đồng xu $3, 4, 5$ lên đầu).
• BBBBAAAA (chuyển các đồng xu $3, 4, 5, 6$ lên đầu).
• ...

Hỏi rằng với dãy $a$ đã cho, tồn tại hay không một cách sắp xếp các đồng xu sao cho không thể có trường hợp $n$ đồng xu đầu tiên có cùng một trạng thái sau một số hữu hạn các thao tác?

4 4
1 2 3 4

NO

4 2
1 2

YES

Cho một dãy số nguyên $a$ gồm $n$ phần tử và một số nguyên dương $k$. Một phần tử $a_i$ được gọi là quan trọng khi và chỉ khi tồn tại một tập các phần tử của dãy $a$ (giá trị có thể trùng nhau nhưng vị trí bắt buộc phải khác nhau) có chứa phần tử $a_i$ sao cho tổng các giá trị trong tập này lớn hơn hoặc bằng $k$, nhưng khi bỏ đi số $a_i$ thì tổng các số lại nhỏ hơn $k$. Hãy xác định xem mỗi phần tử trong dãy $a$ có quan trọng hay không.

4 10 
4 1 6 2

1010

Các bài G, H, I chỉ khác nhau ở giới hạn của $c$.
Cho số nguyên không âm $c$, bạn cần đếm xem có bao nhiêu số nguyên không âm $a ≤ c$ sao cho $(\sqrt c - \sqrt a)^2$ là một số nguyên, hay nói cách khác tồn tại số nguyên không âm $b$ sao cho $\sqrt a + \sqrt b = \sqrt c$.

5
5 
10 
15 
20 
25

2
2 
2 
3 
6

Các bài G, H, I chỉ khác nhau ở giới hạn của $c$.
Cho số nguyên không âm $c$, bạn cần đếm xem có bao nhiêu số nguyên không âm $a ≤ c$ sao cho $(\sqrt c - \sqrt a)^2$ là một số nguyên, hay nói cách khác tồn tại số nguyên không âm $b$ sao cho $\sqrt a + \sqrt b = \sqrt c$.

5
5 
10 
15 
20 
25

2
2 
2 
3 
6

Các bài G, H, I chỉ khác nhau ở giới hạn của $c$.
Cho số nguyên không âm $c$, bạn cần đếm xem có bao nhiêu số nguyên không âm $a ≤ c$ sao cho $(\sqrt c - \sqrt a)^2$ là một số nguyên, hay nói cách khác tồn tại số nguyên không âm $b$ sao cho $\sqrt a + \sqrt b = \sqrt c$.

5
5 
10 
15 
20 
25

2
2 
2 
3 
6

Đây là một bài tập giao tiếp với máy chấm. Bài A và B chỉ khác nhau ở giới hạn n

Có một con mèo và $n$ chiếc hộp được đánh số từ $1$ đến $n$, ở ngày $0$ con mèo đang ở trong một hộp bất kỳ.

Mỗi đêm, nó sẽ bỏ ra chiếc hộp của mình và di chuyển sang chiếc hộp khác ở ngay cạnh chiếc hộp của nó, nói cách khác, nếu con mèo đang ở hộp thứ $i$, nó sẽ đi sang chiếc hộp thứ $i − 1$ (nếu $i − 1 ≥ 1$) hoặc chiếc hộp thứ $i + 1$ (nếu $i + 1 ≤ n$). Mỗi buổi sáng, bạn sẽ đi đến những chiếc hộp và được mở một chiếc hộp. Nếu bạn tìm thấy chú mèo, quá trình kết thúc. Nếu không, bạn đóng chiếc hộp lại và để lại chỗ cũ. Do sự kiên nhẫn của bạn có giới hạn, bạn chỉ có thể thực hiện quá trình này trong không quá $10^5$ ngày.

Đây là một bài tập giao tiếp với máy chấm. Bài A và B chỉ khác nhau ở giới hạn n

Có một con mèo và $n$ chiếc hộp được đánh số từ $1$ đến $n$, ở ngày $0$ con mèo đang ở trong một hộp bất kỳ.

Mỗi đêm, nó sẽ bỏ ra chiếc hộp của mình và di chuyển sang chiếc hộp khác ở ngay cạnh chiếc hộp của nó, nói cách khác, nếu con mèo đang ở hộp thứ $i$, nó sẽ đi sang chiếc hộp thứ $i − 1$ (nếu $i − 1 ≥ 1$) hoặc chiếc hộp thứ $i + 1$ (nếu $i + 1 ≤ n$). Mỗi buổi sáng, bạn sẽ đi đến những chiếc hộp và được mở một chiếc hộp. Nếu bạn tìm thấy chú mèo, quá trình kết thúc. Nếu không, bạn đóng chiếc hộp lại và để lại chỗ cũ. Do sự kiên nhẫn của bạn có giới hạn, bạn chỉ có thể thực hiện quá trình này trong không quá $10^5$ ngày.

Cho một hàm $f$ được viết bằng ngôn ngữ C++ như sau (ở đây ^ là phép $XOR$, & là phép $AND$, << là phép dịch bit):

long long f (long long a, long long b)
{
    if (b == 0) return a;
    else return f(a ^ b, (a & b) << 1);
}

5

5

Tudor dang ngồi trong lớp học toán, ở trước màn hình laptop. Rõ ràng rằng cậu đang không chú ý nghe giảng. Đen cho cậu, cậu bị giáo viên gọi lên để giải một số bài toán. Vì giáo viên cũng không mong đợi gì nhiều ở Turdo, cậu ấy chỉ cần làm một vài phép cộng đơn giản. Tuy nhiên, việc đơn giản với bạn và mình thì chưa chắc đã đơn giản với Turdo. Hãy giúp Turdo làm các bài toán nhé!

Input

Dòng đầu tiên sẽ gồm một số nguyên ~N~ (~1 \le N \le 100\,000~), số phép cộng mà Turdo phải làm. ~N~ dòng tiếp theo sẽ chứa hai số nguyên có giá trị tuyệt đối nhỏ hơn ~1\,000\,000\,000~, chính là hai số nguyên dương mà Turdo phải cộng

Output

In ra ~N~ dòng, mỗi dòng gồm một số nguyên, là tổng của hai số ở dòng tương ứng

Sample Input

    2
    1 1
    -1 0

Sample Output

    2
    -1

Cho một bảng $n$ hàng, $m$ cột. Người ta xét tất cả khả năng điền các số từ $1$ đến $k$ vào bảng. Một ô trong bảng được gọi là cực đại địa phương nếu như nó thoả mãn số được điền lớn hơn tất cả các ô cùng hàng và cùng cột. Hãy đưa ra giá trị $\displaystyle \sum_{g \, = \, 0}^{n \, \cdot \, m} (g + 1) \cdot A(g)$ trong đó $A(g)$ là số cách điền bảng sao cho có chính xác $g$ ô cực đại địa phương.

Input

• Dòng đầu tiên chứa số nguyên $T$ ($1 \le T \le 5$) là số lượng test.
• Trong $T$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $n$, $m$ và $k$ ($1 \leq n, m \leq 10^{10^6}$, $1 \leq k \leq 10^6$) lần lượt là số hàng, số cột của bảng và giá trị tối đa được điền.

Output

• Gồm $T$ dòng, dòng thứ $i$ in ra phần dư trong phép chia đáp án của test thứ $i$ cho $10 ^ 9 + 7$.

Scoring

• Subtask 1 ($10\%$ số điểm): $n \cdot m \le 10$, $k \le 5$.
• Subtask 2 ($20\%$ số điểm): $n, m \le 2000$, $k = 2$.
• Subtask 3 ($30\%$ số điểm): $n, m, k \le 200$.
• Subtask 4 ($30\%$ số điểm): $n, m \le 10^6$.
• Subtask 5 ($10\%$ số điểm): Không có ràng buộc gì thêm.

Example

5
7 1 3
4 2 3
8 1 2
10 1 5
3 3 4

2642
10233
264
12589025
487936

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

1514
135
744625
744625
1184

Bạn được cho $V$ đỉnh của một đồ thị và phải tạo một đồ thị vô hướng liên thông bằng cách nối các đỉnh với các cạnh đều có trọng số là 1. Các đỉnh của đồ thị được đánh số lần lượt từ $1$ đến $V$. Gọi $E$ là số cạnh của đồ thị, $d_i$ là khoảng cách nhỏ nhất từ đỉnh $1$ đến đỉnh $i$ và $S = d_1 + d_2 + ... + d_V$. Hỏi giá trị $(V+E)*S$ có thể có giá trị lớn nhất là bao nhiêu?

Input

• Dòng đầu tiên chứa số testcase $T$.

• $T$ dòng tiếp theo, mỗi dòng chứa một số nguyên dương $V$.

Output

• Gồm $T$ dòng, mỗi dòng chứa giá trị lớn nhất của $(V+E)*S$ trong mỗi testcase. Vì giá trị này có thể rất lớn nên cần in ra phần dư của giá trị đó sau phép chia lấy dư cho $10^9+7$.

Scoring

• $3\%$ số điểm có $T = 1, V \le 7$.

• $22\%$ số điểm có $T \le 10, V \le 1000$.

• $25\%$ số điểm có $T \le 1000, V \le 10^6$.

• $50\%$ số điểm có $T \le 10^5, V \le 10^9$.

1
2

3

1
5

90

1 2
2 3
3 4
4 5

1 2
2 3
3 4
4 5
3 5