# Chef and Sums SOLUTIONS CHEFSUMS

## Chef and Sums SOLUTION

Gourmet specialist gave you a grouping of whole numbers a1,a2,… ,aN and 3 whole numbers K, m and x. We should characterize the accompanying capacities:

G(i1,… ,iK)=gcd(ai1,… ,aiK)

Sx(i1,… ,iK)=axi1+axi2+… +axiK

Pm(i1,… ,iK)=(ai1⋅ai2⋅… ⋅aiK)m

W(T)=smallestprimedivisorofP1(T)

Culinary expert needs you to figure the whole of G(T)⋅W(T)⋅Sx(T)⋅Pm(T) over all K-tuples of records T=(i1,i2,… ,iK) with the end goal that ij∈{1,2,… ,N} for each legitimate j (there are NK of these K-tuples). Since this whole could be tremendous, register it modulo 109+7.

Information

The principal line of the info contains four space-isolated whole numbers N, K, m and x.

The subsequent line contains N space-isolated numbers a1,a2,… ,aN.

Yield

Print a solitary line containing one whole number ∑TG(T)⋅W(T)⋅Sx(T)⋅Pm(T) modulo 109+7.

Requirements

1≤N≤106

1≤K,m,x≤1018

2≤ai≤106 for each legitimate I

N≤10

K≤6

Subtask #2 (20 focuses): for each legitimate I, ai is even

Subtask #3 (75 focuses): unique requirements

Model Input

3 2 1

2 3 4

Model Output

2414

Clarification

Model case 1: We have NK=32=9 potential sets T of records. The comparing summands are:

T=(1,1): gcd(2,2)⋅(21+21)⋅(2⋅2)1⋅2=64

T=(1,2): gcd(2,3)⋅(21+31)⋅(2⋅3)1⋅2=60

T=(1,3): gcd(2,4)⋅(21+41)⋅(2⋅4)1⋅2=192

T=(2,1): gcd(3,2)⋅(31+21)⋅(3⋅2)1⋅2=60

T=(2,2): gcd(3,3)⋅(31+31)⋅(3⋅3)1⋅3=486

T=(2,3): gcd(3,4)⋅(31+41)⋅(3⋅4)1⋅2=168

T=(3,1): gcd(4,2)⋅(41+21)⋅(4⋅2)1⋅2=192

T=(3,2): gcd(4,3)⋅(41+31)⋅(4⋅3)1⋅2=168

T=(3,3): gcd(4,4)⋅(41+41)⋅(4⋅4)1⋅2=1024

Their aggregate modulo 109+7 is 2414.