Trong khi Loli và Minh đi trên đường cao tốc, để Minh không buồn chán Loli đã đố Minh một bài toán sau: Đếm số bộ ba số ~(a, b, c)~ thỏa mãn ~a \times b~, ~a \times c~ và ~b \times c~ đều là một số chính phương với ~1 \le a < b < c \le n~.

Input

• Dòng đầu tiên chứa số nguyên ~T~ - là số test của bài (~1\le T\le 20~).
• ~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~n~ (~1 \le n \le 10^6~).

Output

• ~T~ dòng, mỗi dòng chứa một số nguyên là kết quả số bộ ba (~a, b, c~) thỏa mãn tương ứng với test ở dòng đó.

Sample Input 1

5
10
20
1707
177013
265918

Sample Output 1

1
5
19938
25974765
48116615

Subtask:

• ~20\%~ số điểm có ~T\le 20, n \le 100~.
• ~30\%~ số điểm có ~T\le 20, n \le 10^3~.
• ~20\%~ số điểm có ~T\le 20, n \le 10^5~.
• ~15\%~ số điểm có ~T = 1, n \le 10^6~.
• ~15\%~ số điểm có ~T\le 20, n \le 10^6~.

Loli đang chuẩn bị đồ để đi tuần trăng mật với Minh. Loli sẽ mang một chiếc ba lô có sức chứa tối đa là ~M~. Trong nhà Loli có ~n~ đồ chơi (đồ vật) khác nhau, đánh số từ ~1~ tới ~n~, đồ vật thứ ~i~ có khối lượng ~a_i~ và giá trị ~b_i~. Mỗi đồ vật chỉ được lấy 1 lần duy nhất.

Yêu cầu: Hãy chọn một số đồ vật xếp vào ba lô với điều kiện tổng khối lượng các đồ vật được chọn không vượt quá ~M~ và tổng giá trị của các đồ vật này là lớn nhất.

Input

• Dòng ~1~: Chứa hai số nguyên dương ~n,M~ (~n\le 1000,\ M\le 10^9~);
• Dòng ~2~...~n+1~: Dòng ~i+1~ chứa hai số nguyên ~a_i,b_i~ (~1\le a_i\le M,\ 0\le b_i\le 10~).

Output

• Dòng 1: Ghi ~S~ là tổng giá trị lớn nhất tìm được;
• Dòng 2: Ghi ~k~ - số lượng các đồ vật được lựa chọn;
• Dòng 3: Ghi ~k~ số nguyên lần lượt là chỉ số của các đồ vật được chọn.
• Trường hợp bạn không liệt kê được chỉ số đồ vật đã chọn, bạn chỉ nhận được ~50\%~ số điểm.
• Nếu có nhiều phương án hợp lệ, bạn chỉ cần in ra một phương án bất kỳ.

Sample Input 1

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

Sample Output 1

21
3
1 3 5

Subtask

• Có ~25\%~ số test có ~n\le 20,\ M\le 100~.
• Có ~25\%~ số test có ~n\le 100,\ M\le 10^5~.
• Có ~50\%~ số test không có ràng buộc gì thêm.

Cho mảng ~A~ có ~N~ phần tử. Tính phần dư của phép chia tích các phần tử trong dãy ~A~ đó với ~10^9+7~.

Input

• Gồm một dòng duy nhất chứa ~N+1~ số nguyên, có giá trị từ ~1~ tới ~10^7~, bao gồm các số ~N\ (1 \le N \le 10^5),\ A_1,\ A_2,\ \dots~

Output

• Đáp án của bài toán.

Sample Input 1

3 17 70 13

Sample Output 1

15470

Để thử nghiệm một xe tự hành, người ta tiến hành một thí nghiệm cho xe vượt qua các chướng ngại vật và đi đến đích. Có thể mô tả thí nghiệm này như sau:

Có một lưới ô vuông kích thước ~m \times n~, các hàng đánh số từ 1 đến ~m~ từ trên xuống dưới và các cột đánh số từ 1 đến ~n~ từ trái qua phải; ô nằm ở giao của hàng ~i~ với cột ~j~ ký hiệu là ~(i,j)~. Trên một số ô có vật cản không thể đi qua được, các ô còn lại không có vật cản. Xe tự hành xuất phát từ ô ~(1,1)~. Mỗi bước nó chỉ có thể di chuyển đến ô chung cạnh ở bên phải hoặc bên dưới nếu như các vị trí này còn nằm trong lưới và không có vật cản. Chính xác hơn từ ô ~(i,j)~ xe chỉ có thể di chuyển đến ô ~(i,j+1)~ hoặc ~(i+1,j)~ nếu như các ô này còn trong lưới và không có vật cản. Xe tự hành cần di chuyển đến ô ~(m,n)~.

Viết chương trình đếm xem có bao nhiêu cách khác nhau để di chuyển xe tự hành từ ô ~(1,1)~ đến ô ~(m,n)~ theo quy tắc trên? Hai cách đi được coi là khác nhau nếu như có ít nhất một ô có trên hành trình của cách đi này nhưng không có trên hành trình của cách đi kia.

Input

• Dòng đầu tiên ghi ba số nguyên dương ~m,n,k~ với ~m,n~ là số hàng và số cột của lưới; ~k~ là số lượng ô có vật cản ~(1\le m, n \le 10^5; 0\le k \le 2000)~.
• ~k~ dòng tiếp theo, dòng thứ ~i~ ghi hai số nguyên ~(r_i, c_i)~ thể hiện ~(r_i, c_i)~ là ô chứa vật cản ~(1\le r_i \le m; 1 \le c_i \le n)~.
• Dữ liệu đảm bảo rằng các ô ~(1,1)~ và ~(m,n)~ là các ô không có vật cản.

Output

• Một số nguyên duy nhất là số lượng cách di chuyển khác nhau của xe tự hành từ ô ~(1,1)~ đến ô ~(m,n)~. Vì con số này có thể rất lớn nên chỉ cần in ra phần dư của nó khi chia cho ~10^9 +7~.

Sample Input 1

3 4 2
2 2
2 3

Sample Output 1

2

Subtask

• ~40\%~ số test có ~1 \le m, n, k \le 1000~.
• ~20\%~ số test có ~k = 0;\ 10^4 \le m,n \le 10^5~.
• ~10\%~ số test có ~k = 1;\ 10^4 \le m,n \le 10^5~.
• ~30\%~ số test còn lại có ~1\le k \le 2000;\ 10^4 \le m, n \le 10^5~.