Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

VO17XXX - Ngày xưa có một bài toán (7 điểm)

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 A1, A2,..., AN và một hằng số C. Với số nguyên dương X bất kì, ký hiệu S(X) = CK, 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 109+7.

Giới hạn

- Trong tất cả các test, N <= 105, C <= 109  và Ai <= 3 * 107.

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

- Trong 20% số test tiếp theo, N <= 17 và Ai <= 106.

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

- Trong 35% số test tiếp theo, Ai <= 106.

- 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 23 - 1 tập con khác rỗng của dãy A:
{4} -> GCD = 4 = 22 -> S(GCD) = 71 =  7
{30} -> GCD = 30 = 2*3*5 -> S(GCD) =  73 =  343
{15} -> GCD = 15 = 3*5 -> S(GCD) = 72 =  49
{4, 30} -> GCD = 2 -> S(GCD) = 71 =  7
{4, 15} -> GCD = 1 -> S(GCD) = 70 =  1
{30, 15} -> GCD = 15 = 3*5 -> S(GCD) = 72 =  49
{4, 30, 15} -> GCD = 1 -> S(GCD) = 70 =  1
Đáp số: 7 + 343 + 49 + 7 + 1 + 49 + 1 = 457.


Được gửi lên bởi:VOJ Team
Ngày:2016-12-28
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:VNOI Online 2017, day 2 (By Lăng Trung Hiếu)

hide comments
2018-10-25 03:56:04 minhsn
trau cung AC
2018-01-02 11:58:09
ủa !sao in 2^n-1 lại được 0đ
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.