Coin change problem

You are working as a cashier at a cheerful fair, and you have coins of different denominations. An unlimited number of coins is available for each denomination, and the value of each denomination is known. Determine the number of ways to pay a given amount using the available coin denominations.

For example, if you have $4$ coin denominations with values $8,3,1$, and $2$, the amount $3$ can be paid in the following ways: $\{1,1,1\},\{1,2\}$ and $\{3\}$.

Input

The first line contains two integers: the amount $n(1\le n\le 250)$ and the number of coin denominations $m(1\le m\le 50)$. The second line contains $m$ integers $c_i(1\le c_i\le 50)$, representing the values of the coin denominations. All $c_i$ values are distinct.

Output

Print the number of ways to pay the amount $n$.

Examples