eolymp
bolt
Try our new interface for solving problems
Problems

Coin change problem

Coin change problem

Time limit 1 second
Memory limit 128 MiB

You are working at the cash counter at a fun-fair, and you have different types of coins available to you in infinite quantities. The value of each coin is already given. Can you determine the number of ways of making change for a particular number of units using the given types of coins?

For example, if you have 4 types of coins, and the value of each type is given as 8, 3, 1, 2 respectively, you can make change for 3 units in three ways: \{1, 1, 1\}, \{1, 2\} and \{3\}.

Input data

First line contains two space-separated integers: number of units n~(1 \le n \le 250) and number of coin types m~(1 \le m \le 50). The second line contains m integers c_i~(1 \le c_i \le 50) describing the respective values of each coin type. Each c_i is guaranteed to be distinct.

Output data

Print the number of ways to make change.

Examples

Input example #1
4 3
1 2 3
Output example #1
4
Input example #2
10 4
2 5 3 6
Output example #2
5