## Coin change

Points: 15
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

You have a sum of money $$S$$ and an infinite supply of coins with denominations $$a[i]$$, in how many ways you can make the sum $$S$$ using the given denominations.

Two ways are considered different if the number of coins with a given denomination used in one way is different than the other way.

Imagine having $$S = 4$$ and we have coins with denominations $$a = \{1, 2, 3\}$$, there are 4 ways to make the sum using the given denominations:

• $$[1,1,1,1]$$
• $$[1,1,2]$$
• $$[2,2]$$
• $$[1,3]$$

Note that $$[1,3]$$ and $$[3,1]$$ are equivalent and considered as the sam way, order does not matter.

#### Input Specification

First line contains integer $$1 \leq S \leq 1000$$ and $$1 \leq K \leq 100$$ the sum of money you have and the number of coin denominations. The second line contains $$K$$ distinct integers representing the coin denominations $$1 \leq a[i] \leq S$$

#### Output Specification

Print one integer representing the number of ways to make change for $$S$$.

Since this number can too big, print it modulo $$10^{9} + 7$$

#### Sample Input

4 3
1 2 3

#### Sample Output

4

#### Sample Input

2 1
1

#### Sample Output

1

#### Sample Input

6 4
1 3 4 2

#### Sample Output

9