Do đã quá quen với dãy fibonacci, hôm nay, chúng ta hãy cùng tìm hiểu về dãy tribonacci.

Số tribonacci thứ ~i~ sẽ có công thức truy hồi như sau: ~f[i] = f[i-1] + f[i-2] + f[i-3]~ nếu ~i > 3~, ngược lại ~f[i] = i~ nếu ~i \le 3~.

Cho ~n~ số tribonacci đầu tiên và một số ~k~ (~k \le n~), hay tìm một dãy con bất kì (không nhất thiết phải liên tiếp) của dãy ~n~ số tribonacci này sao cho tổng của các phần tử trong dãy con đó chia hết cho ~k~.

Input

• Gồm một dòng chứa số nguyên dương ~n~ và số nguyên dương ~k~ ~(1 \le k \le n \le 10^5)~

Output

• Dòng đầu in ra số ~q~ là độ dài của dãy con thỏa mãn tìm được, nếu không tồn tại in ra ~-1~.
• Dòng thứ hai in ra ~q~ chỉ số của dãy con tìm được.
• Nếu có nhiều hơn một dãy con thỏa mãn, in ra bất kì kết quả nào.

Subtask

• ~30\%~ số test có ~n \le 20~.
• ~40\%~ số test có ~n \le 2000~.
• ~30\%~ số test còn lại có ~n \le 10^5~.

Sample Test

Input:

5 4

Output:

2
2 4

Giải thích:

• ~5~ phần tử đầu tiên của dãy tribonacci là: 1 2 3 6 11

• Chọn ra phần tử thứ ~2~ và ~4~ có tổng bằng: ~2+6 = 8~ chia hết cho ~4~.

Cho ~n~ điểm trên mặt phẳng ~Oxy~.

Hãy tìm cách tạo ra một đa giác lồi gồm nhiều đỉnh nhất sao cho nó chỉ bao gồm điểm gốc tọa độ (điểm ~(0,0)~) và một số điểm trong ~n~ điểm đã cho.

Input

• Dòng đầu gồm số nguyên dương ~n~.
• ~n~ dòng sau, mỗi dòng gồm hai số ~x_i,y_i~ miêu tả tọa độ của điểm thứ ~i~.

Output

• In ra số đỉnh nhiều nhất tìm được.

Constraints .

• ~1 \le n \le 300~.
• Tọa độ của các điểm đều là số nguyên trong khoảng ~[1,10^4]~.

Subtask

• Sub ~1~ (~30\%~): ~n \le 20~.
• Sub ~2~ (~70\%~): Không giới hạn gì thêm.

Sample Input 1

5
4 2
2 2
2 3
3 2
3 1

Sample Output 1

4

Sample Input 2

10
9 6
1 7
2 2
3 9
8 7
3 2
9 4
3 1
9 7
6 9

Sample Output 2

7

Cho ~A~ là ~1~ ma trận vuông có kích thước ~n \times n~ và ~A~ chỉ gồm các ô có giá trị ~0~ hoặc ~1~. Tìm số nguyên dương ~k~ nhỏ nhất sao cho lũy thừa bậc ~k~ của ma trận ~A~ là ma trận gồm toàn các số ~0~, biết rằng lũy thừa của một ma trận được mô tả như sau:

Input:

• Dòng đầu gồm ~2~ số nguyên ~n~ và ~m~ trong đó ~n~ là kích thước ma trận còn ~m~ là số ô có giá trị bằng ~1~ trên ma trận ~A~.
• ~m~ dòng tiếp theo, trên mỗi dòng có một cặp số ~(i, j)~ ~(1 \leq i, j \leq n)~ là tọa độ của các ô có giá trị bằng ~1~ trên ma trận ~A~, dữ liệu đảm bảo rằng không có cặp số ~(i, j)~ nào xuất hiện ~2~ lần. Một ô có tọa độ ~(i, j)~ nếu như nó nằm tại dòng thứ ~i~ tính từ trên xuống và cột thứ ~j~ tính từ bên trái sang của ma trận ~A~, nếu toạ độ của ô không nằm trong ~m~ cặp số được cho thì ô đó mặc định có giá trị bằng ~0~.

Constraints

• ~1 \leq n \leq 5 \times 10^5~
• ~0 \leq m \leq 5 \times 10^5~

Subtask

• ~10\%~ số test có ~1 \le n \le 4~.
• ~30\%~ số test khác có ~1 \le n \le 60~.
• ~60\%~ số test còn lại không có điều kiện gì thêm.

Output:

• In ra số nguyên dương ~k~ nhỏ nhất hoặc ~-1~ nếu ~k~ không tồn tại.

Sample Input 1:

4 2
1 2
4 3

Sample Output 1:

2

Sample Input 2:

3 3
1 1
2 2
3 3

Sample Output 2:

-1

Explanation

• Ở Sample test 1, dễ thấy ~A^2~ là ma trận toàn ~0~.

• Ở Sample test 2, ma trận ~A~ đã cho được gọi là một Identity matrix, khi lấy lũy thừa bậc ~k~ của một Identity matrix thì giá trị các ô trên ma trận hoàn toàn giữ nguyên.

Nhân dịp sinh nhật Alice được cha mẹ tặng ~n~ bộ xếp chữ, được đánh số từ ~1~ đến ~n~. Bộ xếp chữ thứ ~i~ có ~a_i~ chữ cái "A" và ~b_i~ chữ cái "B". Alice đưa ra một trò chơi như sau: chọn ra hai bộ xếp chữ trong ~n~ bộ, nhóm các chữ cái "A" và chữ cái "B" của hai bộ đã chọn, rồi xếp tất cả chúng thành một hàng ngang. Ví dụ là có ~3~ chữ cái "A" và ~4~ chữ cái "B" thì "ABABABB" và "BBBBAAA" là một trong các cách xếp hợp lệ, và "AAAABBB" là một trong các cách xếp không hợp lệ.

Alice muốn biết: có bao nhiêu cách chọn bộ và xếp chữ như vậy? Hai cách là khác nhau khi hai bộ xếp chữ được chọn ở hai cách là khác nhau, hoặc cách xếp nhận được là khác nhau.

Vì số cách chọn và xếp có thể rất lớn, bạn hãy in ra số cách tìm được chia lấy dư cho ~10^9+7~.

Input

Dòng đầu chứa số nguyên ~n~ (~2 \le n \le 2 \times 10^5~).

~n~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~a_i~, ~b_i~ (~1 \le a_i, b_i \le 2000~).

Output

In ra một số nguyên duy nhất là số cách chọn bộ và xếp chữ tìm được, modulo ~10^9+7~.

Scoring

• Subtask 1 (~20~ điểm): ~n \le 5~; ~a_i, b_i \le 10~.
• Subtask 2 (~20~ điểm): ~n \le 2000~.
• Subtask 3 (~30~ điểm): ~a_i, b_i \le 50~.
• Subtask 4 (~30~ điểm): Không có ràng buộc gì thêm.

Example

Input

2
1 1
2 1

Output

10

Khu rừng ma thuật có ~n~ địa điểm và được kết nối bởi ~n-1~ đường đi, hay nói cách khác, khu rừng chính là một cây!

Địa điểm ~i~ trong khu rừng mọc lên ~a_i~ cây nấm. Marisa muốn hái chúng, nhưng hôm nay cô đang hơi lười nên sẽ sử dụng chiếc máy hái nấm mới mua của Nitori.

Chiếc máy có phạm vi hoạt động là ~r~. Khi sử dụng chiếc máy ở địa điểm ~i~, nó sẽ hái toàn bộ nấm ở các đỉnh ~j~ sao cho đường đi ngắn nhất giữa ~i~ và ~j~ không quá ~r~. Chiếc máy có thể được sử dụng ~k~ lần trước khi hết pin. Hãy tìm cách hái được nhiều nấm nhất giúp Marisa nhé!

Input

• Dòng đầu tiên là ~T~, số lượng bộ dữ liệu.
• ~T~ nhóm dòng sau:
  • Dòng đầu tiên gồm ba số nguyên ~n,k,r~.
  • Dòng thứ hai gồm ~n~ số nguyên ~a_i~.
  • ~n-1~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~u,v~, thể hiện có đường đi giữa địa điểm ~u~ và ~v~.

Output

• Với mỗi bộ dữ liệu, in ra một số nguyên là số nấm nhiều nhất có thể hái được.

Subtask

• Trong toàn bộ các test: ~1 \le k \le n \le 1000~, ~1 \le r \le 1000~, ~1 \le a_i \le 10^6~, ~1 \le u,v \le n~, ~1 \le T \le 5~.
• Subtask ~1~ (~10\%~ số điểm): ~1 \le k \le n \le 20~.
• Subtask ~2~ (~10\%~ số điểm): Cây là đường thẳng.
• Subtask ~3~ (~40\%~ số điểm): ~1 \le k \le n \le 50~, ~0 \le r, a_i \le 50~.
• Subtask ~4~ (~20\%~ số điểm): ~k \le 2, n,r \le1000~.
• Subtask ~5~ (~20\%~ số điểm): Không có giới hạn gì thêm.

Sample Input 1

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

Sample Output 1

46