Huhu. Nghĩ mãi không ra nên viết đề bài này như thế nào...

Cho dãy số nguyên dương ~A_1~, ~A_2~, ..., ~A_N~ và một hằng số ~C~. Với số nguyên dương ~X~ bất kì, ký hiệu ~S(X) = C^K~, với ~K~ là số ước nguyên tố của ~X~. Tính tổng của các giá trị ~S(X)~, trong đó ~X~ là ước chung lớn nhất của một dãy con khác rỗng bất kì của dãy ~A~.

Input

Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~C~

Dòng thứ hai chứa ~N~ số nguyên dương của dãy ~A~.

Output

Ghi ra một số nguyên duy nhất là kết quả của bài toán theo Modulo ~10^9+7~.

Giới hạn

- Trong tất cả các test, ~N \leq 10^5~, ~C \leq 10^9~ và ~A_i \leq 3 \times 10^7~.

- Trong 10% số test đầu tiên, ~C = 1~.

- Trong 20% số test tiếp theo, ~N \leq 17~ và ~A_i \leq 10^6~.

- Trong 25% số test tiếp theo, ~N \leq 1000~ và ~A_i \leq 1000~.

- Trong 35% số test tiếp theo, ~A_i \leq 10^6~.

- Trong 10% số test cuối cùng, không có ràng buộc gì thêm.

Sample Input

3 7
4 30 15

Sample Output

457

Note

Xét ~2^3 - 1~ tập con khác rỗng của dãy ~A~:

~\{4\} \rightarrow GCD = 4 = 2^2 \rightarrow S(GCD) = 7^1 = 7~

~\{30\} \rightarrow GCD = 30 = 2 \times 3 \times 5 \rightarrow S(GCD) = 7^3 = 343~

~\{15\} \rightarrow GCD = 15 = 3 \times 5 \rightarrow S(GCD) = 7^2 = 49~

~\{4, 30\} \rightarrow GCD = 2 \rightarrow S(GCD) = 7^1 = 7~

~\{4, 15\} \rightarrow GCD = 1 \rightarrow S(GCD) = 7^0 = 1~

~\{30, 15\} \rightarrow GCD = 15 = 3 \times 5 \rightarrow S(GCD) = 7^2 = 49~

~\{4, 30, 15\} \rightarrow GCD = 1 \rightarrow S(GCD) = 7^0 = 1~

Đáp số: ~7 + 343 + 49 + 7 + 1 + 49 + 1 = 457~.