/**
 * 
 * Problem Statement-
 * [DP: Coin Change](https://www.hackerrank.com/challenges/ctci-coin-change/problem)
 * 
 */
package com.javaaid.hackerrank.solutions.tutorials.ctci;

import java.util.HashMap;
import java.util.Scanner;

/**
 * @author Kanahaiya Gupta
 *
 */
public class DPCoinChange {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int m = in.nextInt();
		int coins[] = new int[m];
		for (int coins_i = 0; coins_i < m; coins_i++) {
			coins[coins_i] = in.nextInt();
		}
//	        approach1(n, coins);
//	        approach2(n, coins);
		approach3(n, coins);
//	        approach4(n, coins);
		in.close();
	}

	/**
	 * @param n
	 * @param coins
	 */
	private static void approach4(int n, int[] coins) {
		long result = noOfWaysToGetChangeUsingRecursionWithMemo2(coins, n);
		System.out.println(result);
	}

	/**
	 * @param n
	 * @param coins
	 */
	private static void approach3(int n, int[] coins) {
		long result = noOfWaysToGetChangeUsingDP(coins, n);
		System.out.println(result);
	}

	/**
	 * @param n
	 * @param coins
	 */
	private static void approach2(int n, int[] coins) {
		long memo[][] = new long[n + 1][coins.length + 1];
		memo[0][0] = 1;
		long result = noOfWaysToGetChangeUsingRecursionWithMemo(coins, n, 0, memo);
		System.out.println(result);
	}

	/**
	 * @param n
	 * @param coins
	 */
	private static void approach1(int n, int[] coins) {
		long result = noOfWaysToGetChangeUsingRecusion(coins, n, 0);
		System.out.println(result);
	}

	/**
	 * method1 with recursion
	 * 
	 * @param coins
	 * @param n
	 * @return
	 */
	private static long noOfWaysToGetChangeUsingRecusion(int[] coins, int n, int index) {
		if (n == 0)
			return 1;
		if (n < 0 || index >= coins.length)
			return 0;
		return noOfWaysToGetChangeUsingRecusion(coins, n - coins[index], index)
				+ noOfWaysToGetChangeUsingRecusion(coins, n, index + 1);
	}

	/**
	 * method2 with recursion with memorization
	 * 
	 * @param coins
	 * @param n
	 * @return
	 */
	private static long noOfWaysToGetChangeUsingRecursionWithMemo(int[] coins, int n, int index, long[][] memo) {
		if (n == 0)
			return 1;
		if (n < 0 || index >= coins.length)
			return 0;
		if (memo[n][index] != 0)
			return memo[n][index];
		return memo[n][index] = noOfWaysToGetChangeUsingRecursionWithMemo(coins, n - coins[index], index, memo)
				+ noOfWaysToGetChangeUsingRecursionWithMemo(coins, n, index + 1, memo);
	}

	/**
	 * method3 with recursion with memorizaion with hashmap(alternate of method2)
	 * 
	 * @param coins
	 * @param money
	 * @return
	 */
	private static long noOfWaysToGetChangeUsingRecursionWithMemo2(int[] coins, int n) {
		return makeChange(coins, n, 0, new HashMap());
	}

	private static long makeChange(int[] coins, int money, int index, HashMap memo) {
		if (money == 0)
			return 1;
		if (index >= coins.length)
			return 0;

		String key = money + "-" + index;
		if (memo.containsKey(key)) {
			return memo.get(key);
		}

		int amountWithCoin = 0;
		long ways = 0;
		while (amountWithCoin <= money) {
			int remaining = money - amountWithCoin;
			ways += makeChange(coins, remaining, index + 1, memo);
			amountWithCoin += coins[index];
		}
		memo.put(key, ways);
		return ways;
	}

	/**
	 * method4 using dynamic programming approach
	 * 
	 * @param coins
	 * @param n
	 * @param i
	 * @return
	 */
	private static long noOfWaysToGetChangeUsingDP(int[] coins, int n) {
		long dp[] = new long[n + 1];
		dp[0] = 1;
		for (int coin : coins) {
			for (int j = coin; j <= n; j++) {
				dp[j] += dp[j - coin];
			}
		}
		return dp[n];
	}
}