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.


go =>
  Problems = [[      1*100, [25,10,5,1]],            % 1 dollar
              [    100*100, [100,50,25,10,5,1]],   % 100 dollars
              [  1_000*100, [100,50,25,10,5,1]],  % 1000 dollars
              [ 10_000*100, [100,50,25,10,5,1]], % 10000 dollars
              [100_000*100, [100,50,25,10,5,1]] % 100000 dollars
              ],
  foreach([N,L] in Problems)
     initialize_table, % clear the tabling from previous run
     println([n=N,l=L]),
     time(println(num_sols=coins(L,N,1)))
  end.
 
table
coins(Coins, Money, M) = Sum =>
    Sum1 = 0,
    Len = Coins.length,
    if M == Len then
      Sum1 := 1,
    else 
       foreach(I in M..Len)
         if Money - Coins[I] == 0 then
            Sum1 := Sum1 + 1
         end,
         if Money - Coins[I] > 0 then
            Sum1 := Sum1 + coins(Coins, Money-Coins[I], I)
         end,
       end
    end,
    Sum = Sum1.