Exact Money Spending

You are given an amount of money \(M\) (\(M \le 10000\)) and \(N\) dishes (\(N \le 100\)). The \(i\)-th dish costs \(a_i\) dollars (\(a_i \le 1000\)), and each dish is available in only one portion. Little A insists on spending exactly all his money. Determine the number of ways he can select a subset of dishes such that the total cost is exactly \(M\).

Note: It is guaranteed that the execution time does not exceed 1 second.

inputFormat

The first line of input contains two integers \(M\) and \(N\) separated by space.

The second line contains \(N\) integers \(a_1, a_2, \dots, a_N\), where each \(a_i\) represents the cost of the \(i\)-th dish.

outputFormat

Output a single integer representing the number of ways to select dishes so that the sum of their prices is exactly \(M\).

sample

10 4
2 3 5 1

1