This was a classical application of multiplying polynomials using FFT(Fast Fourier Transform). If you don’t know about this refer to this

nice tutorial http://codeforces.com/topic/43659/en13?mobile=true.

In the question we are asked to multiply n polynomials in something around O(nlogn),so a brute force solution(O(n^2)) won’t work.

After multiplying the n polynomials of the form (1 + A[i]*X),the coefficient of X^K in the resulting polynomial will be our answer.

Take care of the MOD thing while performing all the operations.