Setting

Numbers. People generally dislike numbers, but let's ignore that for the time being and instead pretend that numbers are universally loved. Everyone carries heaps of numbers around with them, and you choose to capitalize on that fact. You offer the following (paid) service: given the list of numbers they carry around with them as well as their favourite number (not necessarily in that list), you tell them how many ways there are to combine their numbers such that the sum equals their favourite number. For example, given the list [4, 3, 2, 2, 1, 1] and the favourite number 4, you find that there are four ways to produce that number:

  1. 4
  2. 3 + 1
  3. 2 + 2
  4. 2 + 1 + 1

Note that a number can be used within a sum as many times as it appears in the list, and that a single number counts as a sum.

Input

The input will contain one or more test cases, one per line. Each test case contains \(1 \leq f \leq 1000\), the favourite number, followed by \(1 \leq n \leq 12\), the number of integers in the list, followed by \(n\) integers \(x_1, \ldots, x_n\) with \(1 \leq x_i \leq 100\). If \(n=0\), it signals the end of the input.

Output

For each test case, output a separate line that specifies how many combinations of numbers are possible that sum up to \(f\).

Sample Input

4 6 4 3 2 2 1 1
5 3 2 1 1
400 12 50 50 50 50 50 50 25 25 25 25 25 25
0 0

Sample Output

4
0
2

This is based on challenge 574 of the ACM International Collegiate Programming Contest. Test input is provided by uDebug.

Upload Solution

Please log in to submit your solution.

Statistics

Difficulty (2 votes)
Average test runtime 0.71
Points (changes over time) 10
Tried by 10 users
Solved by 8 users

Global ranking

# Name Runtime Points worth
1 贝尔恩德 0.14 20
2 Pascal 0.15 19
3 ,s/java/NaN/gi 0.16 17
4 Irfan 0.41 7
5 Mac 0.48 6
6 Dark 0.53 5
7 Connor 0.54 5
8 Skøgland 3.27 1