возможная сумма произведения k элементов из массива (допускается повторение)

Question

Учитывая массив из n элементов и число k, мы должны выбрать k элементов из массива и вычислить сумму всех возможных произведений, полученных этими k элементами (допускается повторение); Также два набора из k элементов не должны иметь одинаковые индексы. означает, что порядок не имеет значения.

Примечание: переполнение обрабатывается по модулю некоторого простого числа;

Ограничения : N <= 5000; k <= 1e18; </p>

например ->

arr [] = {1,2,3};

k = 2

возможных k элементов -> 1 * 1 + 1 * 2 + 1 * 3 + 2 * 2 + 2 * 3 + 3 * 3 = 25;

Порядок не имеет значения : 1 * 2 и 2 * 1 здесь не отличаются;

Я сделал рекурсивный код, но не знаю, как преобразовать его в DP.

recur(pos,prod,items)
{
    if(items==k){sum=(sum+prod%prime);return;}

    if(pos==n)return;

    for(int i=0;i<=k-items;i++)
    {
        recur(pos+1,(prod*power(arr[pos],i))%prime,items+i);
    }
}