kh0i có một túi gồm ~n~ cây que, cây que thứ ~i~ có độ dài ~a_i~. kh0i muốn các bạn tính xem có bao nhiêu bộ BA cây QUE khác nhau thỏa mãn chúng tạo với nhau thành một tam giác cân.

Chú ý : ~(a_i,a_j,a_k)~ và ~(a_j,a_k,a_i)~ là hai bộ giống nhau.

Input

• Dòng đầu gồm một số nguyên dương ~n~ ~(3 \le n \le 10^5)~.
• Dòng thứ hai gồm một dãy ~n~ số nguyên dương ~a_1, a_2, \dots, a_{n}~ ~(1 \le a_i \le 10^9)~ là độ dài các cây que.

Output

• In ra đáp số là số bộ thỏa mãn.

Sample Input

5
1 3 2 2 2

Sample Output

7

Notes

• Các bộ thỏa mãn là các vị trí ~(1,3,4)~,~(1,3,5)~,~(1,4,5)~,~(2,3,4)~,~(2,3,5)~,~(2,4,5)~,~(3,4,5)~

Pikachu đang ở ô ~(0,0)~ và cậu ấy muốn đi đến ô ~(n, m)~. Biết rằng khi đang ở ô ~(x,y)~, Pikachu chỉ có thể đi đến ô ~(x + 1, y)~ hoặc ~(x, y + 1)~. Hãy đếm số cách mà Pikachu có thể đi, vì kết quả có thể rất lớn nên hãy in ra theo module ~10^9+7~.

Input

• Dòng một chứa hai số nguyên dương ~t \; (t \leq 1000)~ và ~s~ lần lượt là số bộ dữ liệu của test và subtask của test.
• ~t~ dòng sau, mỗi dòng chứa ~2~ số nguyên dương ~n~ và ~m~ tương ứng với ~1~ bộ dữ liệu.

Output

• Gồm ~t~ dòng, mỗi dòng chứa kết quả của một test theo thứ tự đầu vào.

Subtask

• Sub ~1~: ~n, m \leq 1000~.
• Sub ~2~: ~n, m \leq 10^6~.

Sample Input 1:

3 1
2 2
4 7
5 6

Sample Output 1:

6
330
462

Hãy đếm số hoán vị độ dài ~n~ sao cho: ~a[i] \neq i~, ~\forall 1 \leq i \leq n~. Vì kết quả có thể rất lớn, hãy in ra kết quả lấy phần dư cho ~10^9+7~.

Input

Dòng ~1~: Ghi số nguyên dương ~n~ ~(n≤10^6)~.

Output

Dòng ~1~: Chứa kết quả của bài toán.

Scoring

Sample Input 1

2

Sample Output 1

1

Cho dãy ~A~ gồm ~n~ số nguyên dương: ~a_1,a_2,...,a_n~. Hãy tính:

• ~\prod_{S \subseteq A}^{S \neq 0}gcd(S)~.

Ở đây, ~gcd(S)~ là kí hiệu ước chung lớn nhất của tập ~S~.

Input

• Dòng đầu tiên gồm hai số nguyên ~n~
• Dòng thứ hai gồm ~n~ số nguyên, số thứ ~i~ là ~a_i~.

Constraint

• ~1 \le n \le 10^5~
• ~1 \le a_i \le 10^6~.

Subtask

• Subtask ~1~ ~(30\%)~: ~1 \le n \le 20~.
• Subtask ~2~ ~(30\%)~: ~a_i~ đôi một phân biệt.
• Subtask ~3~ ~(40\%)~: Không có ràng buộc gì thêm.

Output

• In ra kết quả bài toán sau khi chia lấy dư cho ~10^9+7~.

Sample Input 1:

3
1 4 6

Sample Output 1:

48

Cho các số nguyên dương ~a,b,p,x~ trong đó ~p~ là số nguyên tố.

Yêu cầu : Đếm số số nguyên dương ~n~ thỏa mãn ~1 \le n \le x~ và :

$$ ~na \equiv b^n~ ~(\bmod p)~ $$

Input

• Một dòng duy nhất chứa bốn số nguyên dương ~a,b,p,x~.

Output

• In ra kết quả của bài toán .

Scoring

• Subtask 1 ~(10\%)~: ~a,b < p \le 3, x \le 10^{15}~.
• Subtask 2 ~(10\%)~: ~a,b < p \le 10^6+3, x \le 10^7~.
• Subtask 3 ~(80\%)~: ~a,b < p \le 10^6+3, x \le 10^{15}~.

Sample Input 1

3 3 5 15

Sample Output 2

2

Sample Input 1

1 1 2 15

Sample Output 2

7