```
#include<bits/stdc++.h>
using namespace std;
long long int getWays(vector<long long int>coins, long long int n, long long int m)
{
long long int dp[m][n+1], p;
for(int j=1;j<=n;j++)
{
if(j==coins[j]||(j%coins[0])==0)
dp[0][j] = 1;
else
dp[0][j] = 0;
}
for(int i=1;i<m;i++)
{
for(int j=1;j<=n;j++)
{
if(coins[i]>=j)
{
dp[i][j] = dp[i-1][j];
if(coins[i] == j)
dp[i][j]+= 1;
}
else
{
if(j>=(coins[i]*2))
{
dp[i][j] = dp[i-1][j]+dp[i][(j-coins[i])];
}
else {
dp[i][j] = dp[i-1][j]+dp[i-1][(j-coins[i])];
p = (j%coins[i])?0:1;
dp[i][j]+=p;
}
}
}
}
return dp[m-1][n];
}
int main()
{
long long int n,m,i;
scanf("%lld%lld",&n,&m);
vector<long long int>coins(m);
for(i=0;i<m;i++)
{
scanf("%lld",&coins[i]);
}
if(n==0)
cout<<0;
else {
cout<<getWays(coins, n, m);
}
return 0;
}
```

**Problem Description**

How many different ways can you make change for an amount, given a list of coins? In this problem, your code will need to efficiently compute the answer.

Task

Write a program that, given

1.The amount N to make change for and the number of types M of infinitely available coins

2. A list of M coins – C={C1, C2, C3,…,CM}

Prints out how many different ways you can make change from the coins to STDOUT.

Input Format

First line will contain 2 integer N and M respectively.

Second line contain M integer that represent list of distinct coins that are available in infinite amount.

Constraints

1<=Ci<=50

1<=N<=250

1<=M<=50

The list of coins will contain distinct integers.

Output Format

One integer which is the number of ways in which we can get a sum of N from the given infinite supply of M types of coins.**Test Case 1**

**Input (stdin)**4 3

1 2 3

**Expected Output**4**Test Case 2**

**Input (stdin)**10 4

2 5 3 6

**Expected Output**5