Hôm nay bin9638, vị thần tham lam nhận được một câu đố của vị thần ngu dốt algorit.

algorit cho bin9638 một dãy \(n\) điểm có tọa độ \(x,y\) \((|x|,|y| \le 10^9)\) trên mặt phẳng tọa độ. algorit đố bin9638 với \(n\) điểm trên thì có bao nhiêu cặp đường thẳng vuông góc sao cho mỗi đường thẳng nối \(2\) điểm phân biệt bất kì trong \(n\) điểm trên.

Nếu bin9638 giải ra thì sẽ nhận được một cái nịt siêu to khổng lồ từ algorit, các bạn hãy giúp bin9638 nhé !

Input

• Dòng đầu tiên là số \(n\).
• \(n\) dòng tiếp theo mỗi dòng chứa 2 số nguyên \(x,y\) là tọa độ của điểm tương ứng.

Output

• \(1\) số duy nhất là kết quả.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n \le 10\)
• Subtask \(2\) (\(50\%\) số điểm): \(n \le 1000\)

Example

4
1 0
0 2
0 1
-1 0

2

5
1 0
0 -1
0 1
-1 0
2 0

7

bin9638, em trai Hùng Bá, cũng là một tay định giá thứ thiệt. Khác với anh mình chuyên định giá tiền thì bin9638 lại chuyên định giá những que diêm. Ở nhà của anh có rất nhiều que diêm, từ diêm có gỗ được lấy từ những cây gỗ quý từ rừng rậm Amazon, diêm cổ \(1000\) tuổi, diêm được mạ vàng,....

Một hôm vì thấy định giá diêm mãi cũng chán nên bin9638 nghĩ ra trò mới với những que diêm của mình. bin9638 bắt đầu dùng những que diêm của mình để xếp hình, anh bắt đầu với hình mình thích nhất là hình chữ nhật. Hiện tại bộ sưu tầm diêm của bin9638 có \(n\) que diêm có độ dài \(A_1, A_2, A_3, .... A_n\) \(( 1 \le A_i \le 10^9 )\), anh ấy muốn biết là với bộ sưu tầm này thì có thể chọn ra bao nhiêu bộ \(4\) que diêm để chúng có thể tạo thành hình chữ nhật.

bin9638 cứ xếp mãi vẫn chưa xong, nên bây giờ anh ấy muốn nhờ các bạn chuyên tin giải giúp. Nếu giúp thành công thì còn được bin9638 tặng \(1\) que diêm mạ inox nữa nhé !

Input

• Dòng đầu tiên là số \(n\).
• Dòng tiếp theo là dãy \(A\).

Output

• \(1\) số duy nhất là phần dư của kết quả khi chia cho \(10^9 + 7\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 100\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \le 300\).
• Subtask \(3\) (\(20\%\) số điểm): \(n \le 3000\).
• Subtask \(4\) (\(40\%\) số điểm): \(n \le 2*10^5\).

Example

6
1 2 1 2 1 3

3

bin9638 là một cậu học sinh rất có duyên với số \(4\), cậu có \(4\) người bạn gái, \(4\) năm học sinh giỏi, \(4\) cái máy tính,..... Bởi vậy từ lâu cậu đã coi số \(4\) là con số may mắn của đời mình.

Hôm nay trên lớp bin9638 được thầy giáo toán học algorit giảng bài về ước của các số, vậy nên bin9638 cũng đã nghĩ về một vấn đề toán học liên quan đến con số \(4\) của mình. Cậu tự hỏi nếu có \(1\) dãy số tự nhiên từ \(l\) đến \(r\) thì trong dãy đó có bao nhiêu số tự nhiên có đúng \(4\) ước nguyên dương.

bin9638 vì suy nghĩ bài toán này liên tiếp \(4\) ngày \(4\) đêm đến mất ăn mất ngủ mà vẫn chưa xong. Vì vậy các bạn hãy giúp cậu ấy nhé, nếu làm được thì sẽ được bin9638 tặng một món quà đấy !

Input

• Dòng đầu tiên là số truy vấn \(Q\).
• \(Q\) dòng tiếp theo mỗi dòng là hai số nguyên dương \(l\) và \(r\).

Output

• \(Q\) dòng là kết quả của các truy vấn tương ứng.

Example

1
7 9

1

Scording

• \(30\)% test có \(Q ≤ 10\) và \(l,r ≤ 10^5\).
• \(30\)% test có \(Q ≤ 100\) và \(l,r ≤ 10^7\).
• \(40\)% test có \(Q ≤ 10^5\) và \(l,r ≤ 10^7\).

algorit là một nhà toán học đại tài, người có chỉ số iq cao nhất nhân loại nếu đếm ngược. Đặc biệt anh rất thích thú với những thứ to và nhỏ, các con số không phải là ngoại lệ. Bởi vậy hôm nay algorit đang thắc mắc một bài toán như sau :

Bạn được cung cấp một dãy số gồm \(n\) số nguyên \(A_1,A_2,...,A_n\).

Nhiệm vụ của bạn là đếm số lượng đoạn con có \(max - min = k\). Ở đây \(max\) và \(min\) là giá trị lớn nhất và giá trị nhỏ nhất của đoạn con đó.

algorit suy nghĩ bài toán này đến mức hói cả đầu mà vẫn chưa nghĩ ra, các bạn hãy giúp algorit nhé !

Input

• Dòng đầu tiên gồm 2 số nguyên \(n,k(0 \le k \le 10^9)\).
• Dòng thứ 2 gồm \(n\) số nguyên \(A_1,A_2,A_3,...,A_n(-10^9 \le A_i \le 10^9)\).

Output

• Gồm một số nguyên duy nhất là số lượng đoạn con thỏa mãn.

Scoring

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

Example

5 2
1 2 1 3 3

6

Chị em Liên và An là hai đứa trẻ được mẹ giao trông coi một cửa hàng tạp hoá nhỏ xíu tại một phố huyện nghèo bên cạnh ga xe lửa, để giúp gia đình vốn đã lao đao: cha mất việc, cả nhà phải bỏ Hà Nội chuyển về sinh sống ở quê. Cũng như nhiều người dân lam lũ tại phố huyện, hai chị em Liên, An vừa bán hàng vừa trông chờ chuyến tàu đêm từ Hà Nội về, ầm ầm lăn bánh qua phố huyện rồi khuất dạng, im tiếng trong trời đêm sâu thẳm. Lúc đó người buôn bán ở phố huyện mới dọn hàng sau một tối ế ẩm để trở về nhà. Còn hai đứa trẻ dần dần chìm vào giấc ngủ yên tĩnh.

Sáng hôm sau đúng \(3h\) sáng chị em Liên và An thức dậy, vẫn trông coi cửa hàng tạp hóa như bình thường thì có một quý ông vào mua thuốc lá. Quý ông này là một người quý tộc và không ai khác đó chính là algorit. Sau khi quý ông mua xong bao thuốc lá, ông này đã đặt câu đố cho chị em Liên và An, quý ông này cho Liên một số nguyên dương \(A\) và An một số nguyên dương \(B\). Liên và An lấy hai số đó cộng lại với nhau thì được số mới, số mới được đưa cho An và Liên sẽ nhận lấy số cũ của An số của Liên hiện tại. Việc đó được lặp đi lặp lại \(n\) lần hay có thể tổng quát nó như sau.

• \(f(1) = A\)
• \(f(2) = B\)
• \(f(n) = (f(n - 1) + f(n - 2))\) \(mod\) \(C\)

Yêu cầu của quý ông này là sau khi sắp xếp lại các giá trị của \(f(1),f(2),f(3),...,f(n)\) theo thứ tự tăng dần thì số thứ \(k(k \le n)\) mang giá trị là bao nhiêu. Quý ông này sẽ thưởng cho hai chị em một bao thuốc lá nếu trả lời đúng. Hãy giúp chị em Liên và An giải bài toán trên nhé.

Input

• Dòng đầu tiên gồm một số nguyên dương \(T(T \le 10)\) là số lượng câu hỏi.
• Mỗi câu hỏi tương ứng với \(5\) số nguyên dương \(n,C,k,A,B(A,B \le 10^{18})\).

Output

• Gồm \(T\) dòng, mỗi dòng là đáp án của câu hỏi tương ứng theo thứ tự.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n,C \le 10^5\).*
• Subtask \(2\) (\(50\%\) số điểm): \(n \le 10^{18},C \le 10^5\).*

Example

1
8 15 7 1 1 

8

Hôm nay algorit đang đi dạo phố thì thấy một trò chơi ven đường như sau :

Cho hai xâu ký tự \(A\) và \(B\) chỉ bao gồm các chữ cái in hoa (từ '\(A\)' tới '\(Z\)'). Người ta muốn cắt xâu \(A\) ra thành các xâu khác rỗng sao cho mọi xâu nhận được sau khi cắt đều xuất hiện trong xâu \(B\).

Hai cách được xem là khác nhau nếu tồn tại vị trí cắt khác nhau trong hai cách.

• Yêu cầu : Hãy đếm số cách cắt thỏa mãn yêu cầu trên.

Input

• Hai dòng đầu chứa xâu \(A\) và \(B\).

Output

• Gồm một số nguyên duy nhất là đáp án của bài toán sau khi chia lấy dư cho \(10^9 + 7\).

Scoring

• Gọi \(f(X)\) là số lượng kí tự của xâu \(X\).
• Subtask \(1\) (\(20\%\) số điểm): \(f(A),f(B) \le 100\).
• Subtask \(2\) (\(20\%\) số điểm): \(f(A),f(B) \le 300\).
• Subtask \(3\) (\(20\%\) số điểm): \(f(A),f(B) \le 10^3\).
• Subtask \(4\) (\(20\%\) số điểm): \(f(A) \le 10^5 , f(B) \le 10^3\).
• Subtask \(5\) (\(20\%\) số điểm): *\(f(A),f(B) \le 3 * 10^5\).

Example

CAB
ABCZ

2

CBA
ABCC

1