import java.util.Arrays;
import java.math.BigInteger;

class CountTheCoins {
    private static BigInteger countChanges(int amount, int[] coins){
        final int n = coins.length;
        int cycle = 0;
        for (int c : coins)
            if (c <= amount && c >= cycle)
                cycle = c + 1;
        cycle *= n;
        BigInteger[] table = new BigInteger[cycle];
        Arrays.fill(table, 0, n, BigInteger.ONE);
        Arrays.fill(table, n, cycle, BigInteger.ZERO);

        int pos = n;
        for (int s = 1; s <= amount; s++) {
            for (int i = 0; i < n; i++) {
                if (i == 0 && pos >= cycle)
                    pos = 0;
                if (coins[i] <= s) {
                    final int q = pos - (coins[i] * n);
                    table[pos] = (q >= 0) ? table[q] : table[q + cycle];
                }
                if (i != 0)
                    table[pos] = table[pos].add(table[pos - 1]);
                pos++;
            }
        }

        return table[pos - 1];
    }

    public static void main(String[] args) {
        final int[][] coinsUsEu = {{100, 50, 25, 10, 5, 1},
                                   {200, 100, 50, 20, 10, 5, 2, 1}};

        for (int[] coins : coinsUsEu) {
            System.out.println(countChanges(     100,
                Arrays.copyOfRange(coins, 2, coins.length)));
            System.out.println(countChanges(  100000, coins));
            System.out.println(countChanges( 1000000, coins));
            System.out.println(countChanges(10000000, coins) + "\n");
        }
    }
}