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.


func cc(_)                { 0 }
func cc({ .is_neg  }, *_) { 0 }
func cc({ .is_zero }, *_) { 1 }
 
func cc(amount, first, *rest) is cached {
    cc(amount, rest...) + cc(amount - first, first, rest...);
}
 
func cc_optimized(amount, *rest) {
    cc(amount, rest.sort_by{|v| -v }...);
}
 
var x = cc_optimized(100, 1, 5, 10, 25);
say "Ways to change $1 with common coins: #{x}";
 
var y = cc_optimized(1000 * 100, 1, 5, 10, 25, 50, 100);
say "Ways to change $1000 with addition of less common coins: #{y}";