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~.
Comments