Giải bài trực tuyến

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₁, A₂,..., 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⁹+7.

Giới hạn

- Trong tất cả các test, N <= 10⁵, C <= 10⁹  và A_i <= 3 * 10⁷.

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

- Trong 20% số test tiếp theo, N <= 17 và A_i <= 10⁶.

- Trong 25% số test tiếp theo, N <= 1000 và A_i <= 1000.

- Trong 35% số test tiếp theo, A_i <= 10⁶.

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

Example

Input:
3 7
4 30 15

Output:
457

Giải thích

Xét 2³ - 1 tập con khác rỗng của dãy A:
{4} -> GCD = 4 = 2² -> S(GCD) = 7¹ =  7
{30} -> GCD = 30 = 2*3*5 -> S(GCD) =  7³ =  343
{15} -> GCD = 15 = 3*5 -> S(GCD) = 7² =  49
{4, 30} -> GCD = 2 -> S(GCD) = 7¹ =  7
{4, 15} -> GCD = 1 -> S(GCD) = 7⁰ =  1
{30, 15} -> GCD = 15 = 3*5 -> S(GCD) = 7² =  49
{4, 30, 15} -> GCD = 1 -> S(GCD) = 7⁰ =  1
Đáp số: 7 + 343 + 49 + 7 + 1 + 49 + 1 = 457.