Score Combinations

You are given a target score (T) and a list of possible play scores. Your task is to compute the number of different ordered sequences of plays that sum exactly to (T). Formally, let (dp[i]) denote the number of ways to get a score of (i) and the recurrence is given by: [ dp[i] = \sum_{\text{play}\ in\ plays ;\text{with}\ i \ge play} dp[i - play] ] with the base case (dp[0]=1). If there are no plays available and (T > 0), the answer is 0. This is a classic dynamic programming problem, similar to the coin change problem with order sensitivity.

inputFormat

The input is read from standard input (stdin). The first line contains a single integer (T) (the target score). The second line contains a single integer (N) representing the number of possible plays. The third line contains (N) space-separated integers, each representing a possible play score.

outputFormat

Output a single integer to standard output (stdout) representing the number of different ways to achieve the target score using the given plays.## sample

4
3
1 2 3

7