I am trying to find the given sum modulo prime
Given n integers and a number $D$ you have to calculate $(a_1 + a_2 + \cdots + a_n)^D$ but the twist here is that there coefficient should not be considered in sum ;
e.g $(a+b)^2 = a^2 + b^2 + 2ab$;
But , required sum is $a^2 + b^2 + ab$;
e.g $(2+6+7)^2=15^2=225$
But , required sum is : $2^2 + 6^2 + 7^2 + 6\cdot7 + 2\cdot7 + 2\cdot6 = 157$
Constraints :
$N\le5000$ (elements where each element $\le10^5$)
$D\le10^{18}$; (Power)
Any hint will be helpful :)