## Coin change

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`

## Comments

Can someone help? I get

"[RTE] Segmentation Error" Dans case 4. Can someone see what is wrong with my code? https://ideone.com/g14chK Thank you very much.Just change your dp array size dp[1001][101]

Thank you a lot :) It worked