There are four types of common coins in   US   currency:

   quarters   (25 cents)
   dimes   (10 cents)
   nickels   (5 cents),   and 
   pennies   (1 cent) 


There are six ways to make change for 15 cents:

   A dime and a nickel 
   A dime and 5 pennies
   3 nickels
   2 nickels and 5 pennies
   A nickel and 10 pennies
   15 pennies


Task

How many ways are there to make change for a dollar using these common coins?     (1 dollar = 100 cents).



Optional

Less common are dollar coins (100 cents);   and very rare are half dollars (50 cents).   With the addition of these two coins, how many ways are there to make change for $1000?

(Note:   the answer is larger than   232).



References

 an algorithm from the book Structure and Interpretation of Computer Programs.
 an article in the algorithmist.
 Change-making problem on Wikipedia.


$ include "seed7_05.s7i";
  include "bigint.s7i";
 
const func bigInteger: changeCount (in integer: amountCents, in array integer: coins) is func
  result
    var bigInteger: waysToChange is 0_;
  local
    var array bigInteger: t is 0 times 0_;
    var integer: pos is 0;
    var integer: s is 0;
    var integer: i is 0;
  begin
    t := length(coins) times 1_ & (length(coins) * amountCents) times 0_;
    pos := length(coins) + 1;
    for s range 1 to amountCents do
      if coins[1] <= s then
        t[pos] := t[pos - (length(coins) * coins[1])];
      end if;
      incr(pos);
      for i range 2 to length(coins) do
        if coins[i] <= s then
          t[pos] := t[pos - (length(coins) * coins[i])];
        end if;
        t[pos] +:= t[pos - 1];
        incr(pos);
      end for;
    end for;
    waysToChange := t[pos - 1];
  end func;
 
const proc: main is func
  local
    const array integer: usCoins is [] (1, 5, 10, 25, 50, 100);
    const array integer: euCoins is [] (1, 2, 5, 10, 20, 50, 100, 200);
  begin
    writeln(changeCount(    100, usCoins[.. 4]));
    writeln(changeCount( 100000, usCoins));
    writeln(changeCount(1000000, usCoins));
    writeln(changeCount( 100000, euCoins));
    writeln(changeCount(1000000, euCoins));
  end func;