Cho hai số nguyên dương ~n~ và ~k~.

Ta có thể xây dựng một dãy số nguyên dương ~a~ gồm ~n~ phần tử: ~a_1,a_2,...,a_n~ sao cho với mọi ~1 \le i \le n~ thỏa mãn điều kiện ~a_i \in [1,k]~.

Gọi ~g(a)~ là ước chung lớn nhất của dãy số ~a~.

Nhiệm vụ của bạn chính là tính tổng ~g(a)~ của mọi dãy số có thể xây dựng (có ~k^n~ dãy số như vậy).

Vì kết quả có thể rất lớn, hãy in nó ra theo module ~10^9+7~.

Input: nhập vào từ file "SUMGCD.INP"

• Gồm một dòng chứa hai số nguyên dương ~n,k~ ~(1 \le n \le 10^9, 1 \le k \le 10^6)~.

Output: ghi ra file "SUMGCD.OUT"

• In ra kết quả theo module ~10^9+7~.

Subtask

• Subtask ~1~ ~(20\%)~: ~n,k \le 7~
• Subtask ~2~ ~(20\%)~: ~n \le 10^5, k = 4~
• Subtask ~3~ ~(25\%)~: ~n \le 10^5, k \le 20~
• Subtask ~4~ ~(20\%)~: ~k \le 10^5~
• Subtask ~5~ ~(15\%)~: Không giới hạn gì thêm.

Ví dụ

Sample Input 1

1  5

Sample Output 1

15

Sample Input 2

5 4

Sample Output 2

1060

Sample Input 3

3 2

Sample Output 3

9

Giải thích

Ở ví dụ ~3~ ta có:

• ~g([1,1,1]) = 1~
• ~g([1,1,2]) = 1~
• ~g([1,2,1]) = 1~
• ~g([1,2,2]) = 1~
• ~g([2,1,1]) = 1~
• ~g([2,1,2]) = 1~
• ~g([2,2,1]) = 1~
• ~g([2,2,2]) = 2~

Kết quả thu được là ~9~.

Ta có định nghĩa ~div(i)~ là số lượng ước số của số nguyên dương ~i~. Ví dụ ~div(3) = 2; div(6) = 4~.

Gọi ~S(n,m)~ là tập các số nguyên dương thỏa mãn ~div(i) = n~ và các thừa số nguyên tố của ~i~ đều bé hơn hoặc bằng số nguyên tố thứ ~m~. Ví dụ, ~S(2,3) = \{2,3,5\}~ vì số nguyên tố thứ ~3~ là ~5~.

Bạn hãy in ra số lượng phần tử trong tập ~S(n,m)~. Con số này có thể rất lớn nên hãy in ra theo modulo ~10^9+7~.

Input

• Dòng đầu chứa hai số nguyên dương ~t~ ~(1 \le 2 \times 10^5)~.
• ~t~ dòng sau, mỗi dòng gồm hai số nguyên dương ~n,m~ thể hiện truy vấn ~(1 \le n \le 2 \times 10^6, 1 \le m \le 10^9)~.

Output

• Với mỗi truy vấn, in ra kết quả.

Subtask:

• Subtask ~1~: ~t,n,m \le 10~ ~(30\%)~
• Subtask ~2~: ~t = 1, m \le 10^5~ ~(30\%)~
• Subtask ~3~: Không có ràng buộc gì thêm. ~(40\%)~

Sample Input 1

3
2 3
4 4
3 5

Sample Output 1

3
10
5

Duck vừa được tặng một món quà là một tấm bảng gồm ~m~ dòng và ~n~ cột, mỗi ô của bảng chứa một chữ cái.

Với tấm bảng vừa nhận được Duik liền nghĩ ra một trò chơi như sau, Duck sẽ xuất phát từ ô ~(1,\ 1)~ và đi đến ô ~(m,\ n)~, ở mỗi bước đi chỉ được đi sang phải hoặc xuống dưới so với ô Duck đang đứng. Khi đi qua mỗi ô Duck ghi lại chữ cái của ô đó để tạo thành một xâu ~s~ gồm ~m + n - 1~ kí tự khi đi đến ô ~(m,\ n)~.

Vì rất yêu thích món quà được tặng nên Duck quyết định sẽ thử mọi cách đi từ ô ~(1,\ 1)~ đến ô ~(m,\ n)~ và tạo ra tất cả các xâu có thể. Cuối cùng Duck nghĩ ra một công thức tính điểm như sau: với mỗi xâu ~s~, nếu có ~f(s)~ cách đi để tạo thành xâu ~s~ thì Duck sẽ được ~f(s)^2~ điểm.

Vì số lượng cách đi cũng như số lượng xâu tạo ra quá lớn khiến cho Duck không thể tự mình tính toán số điểm theo như công thức mà mình đã đề ra. Bạn hãy giúp Duck tính số điểm của mình nhé.

Input

Dòng đầu nhập hai số nguyên ~m~ và ~n~ ~(m \times n \leq 10^5)~ tương ứng là số hàng và cột của bảng.

~m~ dòng tiếp theo mỗi dòng nhập một xâu gồm ~n~ kí tự miêu tả một hàng trong bảng.

Output

Một số nguyên duy nhất là số điểm mà Duck nhận được (modulo ~10^9 + 7~).

Scoring

Subtask 1 (~30\%~): ~m,n \le 10~

Subtask 2 (~30\%~): ~m\times n \le 5000~

Subtask 3 (~40\%~): Không có điều kiện gì thêm

Sample Input 1

3 4
aaaa
aaab
abaa

Sample Output 1

34

Notes

Trong test ví dụ, Khi thử tất cả cách đi từ ô ~(1,\ 1)~ đến ô ~(m,\ n)~ sẽ tạo ra các xâu sau:

• ~3~ xâu aaaaaa

• ~4~ xâu aaaaba

• ~3~ xâu aaabaa

Số điểm nhận được là ~3^2 + 4^2 + 3^2 = 34~

Cho dãy ~a_1,a_2,...,a_n~ gồm các số nguyên dương. Bạn được thực hiện thao tác sau trong khoảng từ ~0~ đến ~k~ lần:

• Chọn ra hai vị trí ~i,j~ ~(1 \le i, j \le n; i \neq j)~. Tăng ~a_i~ lên ~1~ và giảm ~a_j~ đi ~1~.

Bài toán đặt ra là cần tìm số nguyên dương ~D~ lớn nhất sao cho sau khi thực hiện các thao tác, ~a_i~ chia hết cho ~D~ ~\forall i \in [1,n]~.

Input

• Dòng đầu tiên gồm hai số nguyên ~n,k~ ~(2 \le n \le 500, 0 \le k \le 10^9)~
• Dòng thứ hai gồm ~n~ số nguyên, số thứ ~i~ là ~a_i~ ~(1 \le a_i \le 10^6)~.

Output

• In ra số nguyên ~D~ tìm được.

Sample Input 1:

8 7
7 1 6 5 2 8 6 5

Sample Output 1:

5

Cho đồ thị đơn vô hướng gồm ~n~ đỉnh và ~m~ cạnh.

Có ~q~ câu hỏi, mỗi câu hỏi bạn nhận được một giá trị ~k~, tìm cách thêm đúng ~k~ cạnh vào đồ thị sao cho số cạnh cầu của đồ thị mới là ít nhất. Lưu ý rằng bắt đầu mỗi truy vấn, chúng ta chỉ xem xét với đồ thị gốc.

Input

• Dòng đầu chứa ba số nguyên ~n,m,q~ ~(1 \le n,q \le 10^5)~ và ~(1 \le m \le 2 \times 10^5)~.
• ~m~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~u_i, v_i~ ~(1 ≤ u_i, v_i ≤ n; u_i ≠ v_i)~.
• ~q~ dòng sau, mỗi dòng gồm một số nguyên ~k~ miêu tả truy vấn.

Output

• Mỗi dòng in ra kết quả tương ứng của truy vấn là số cạnh cầu bị xóa.

Subtask

• Subtask ~1~: ~q = 1~ và đồ thị là cây. ~(20\%)~
• Subtask ~2~: ~q = 1, k = 1, n \le 10^3~. ~(20\%)~
• Subtask ~3~: ~q = 1, k = 1, n \le 10^5~. ~(20\%)~
• Subtask ~4~: ~q = 1~ ~(20\%)~.
• Subtask ~5~: Không có ràng buộc gì thêm ~(20\%)~.

Sample Input 1

3 2 1
1 2
2 3
1

Sample Output 1

2