Saksham is shopping in a super market which provides a superb offer. If a customer purchases exactly (but not necessarily distinct) n items such that the total cost is divisible by m, a massive cashback is provided. There are l different categories of products with every category having an infinite amount of products. Saksham being a geek, wonders how many possible ways are there to purchase items in such a way that he could get the cashback.
Help him find the number of ways possible to make the purchase.
As this number can be large, you need to print the answer modulo 10^9 + 7.
INPUT
The first line of input contains three space separated integers n, m and l.
The second line of the input contains l space separated integers denoting the cost of each product type.
OUTPUT
You have to print one line, the number of different ways to purchase the items in order to get the cashback, modulo 10^9 + 7.
I done this question using recursion it showing TLE can you please tell how can i use DP in this question