Сумма кратна k

Сколько существует наборов чисел из списка — возможно, пустых, — сумма которых делится на $k$? Пустой набор имеет сумму 0 и потому подходит всегда.

В первой строке числа $n$ от $1$ до $18$ и $k$ от $1$ до $100$. Во второй — $n$ чисел от $1$ до $10^9$.

Одно число.