/////// coin change by matrix// un finished

/////// coin change by matrix// un finished
#include<bits/stdc++.h>
using namespace std;
#define scInt(x) scanf("%d",&x)
int dp[1000][1000];
vector<int > coins;
int start;
int samne_jabo_koi_ghor;
int coinChange(int am)
{


    int i,j;
    if(dp[coins[coins.size()-1]][am])
       return dp[coins[coins.size()-1]][am];
    for(i=0; i<coins.size(); i++)
    {
        for(j=0; j<=am; j++)
        {

            if(j==0)
            {

                dp[coins[i]][j]=1;
                printf("  dp[%d][%d]=%d \n",coins[i],j,dp[coins[i]][j]);
                continue;
            }
            else if(coins[i]==0)
            {

                dp[coins[i]][j]=0;
                printf("  dp[%d][%d]=%d \n",coins[i],j,dp[coins[i]][j]);
                continue;
            }
            if(coins[i]<j){
            dp[coins[i]][j]= dp[coins[i-1]][j] ;
            printf("  dp[%d][%d]=%d \n",coins[i],j,dp[coins[i-1]][j]);
            continue;
            }
            else if(coins[i]==j){
             dp[coins[i]][j]= dp[coins[i-1]][j]+1 ;
                samne_jabo_koi_ghor=j;
                printf("  dp[%d][%d]=%d \n",coins[i],j,dp[coins[i-1]][j]);
            continue;
            }
            dp[coins[i]][j]= dp[coins[i-1]][j]+dp[coins[i]][j-samne_jabo_koi_ghor] ;

        }

    }

           return dp[coins[coins.size()-1]][am];

}



int main()
{
    start=0;

    int n,r,i,tem,amount;
    puts ("enter number of coins the coins");
   scInt(n);

        coins.push_back(0);
        for(i=1; i<=n; i++)
        {
            scInt(tem);
            coins.push_back(tem);
        }
        scInt(amount);

        printf("ways to have %d: %d\n",amount ,coinChange(amount));

        while(scInt(amount)!=EOF){
             puts ("\n\nenter amount");
             printf("ways to have %d: %d\n",amount ,coinChange(amount));

       }






}