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.


*        count the coins           04/09/2015
COINS    CSECT
         USING  COINS,R12
         LR     R12,R15
         L      R8,AMOUNT          npenny=amount
         L      R4,AMOUNT
         SRDA   R4,32
         D      R4,=F'5'
         LR     R9,R5              nnickle=amount/5
         L      R4,AMOUNT
         SRDA   R4,32
         D      R4,=F'10'
         LR     R10,R5             ndime=amount/10
         L      R4,AMOUNT
         SRDA   R4,32
         D      R4,=F'25'
         LR     R11,R5             nquarter=amount/25
         SR     R1,R1              count=0
         SR     R4,R4              p=0
LOOPP    CR     R4,R8              do p=0 to npenny
         BH     ELOOPP
         SR     R5,R5              n=0
LOOPN    CR     R5,R9              do n=0 to nnickle
         BH     ELOOPN
         SR     R6,R6
LOOPD    CR     R6,R10             do d=0 to ndime
         BH     ELOOPD
         SR     R7,R7              q=0
LOOPQ    CR     R7,R11             do q=0 to nquarter
         BH     ELOOPQ
         LR     R3,R5              n
         MH     R3,=H'5'
         LR     R2,R4              p
         AR     R2,R3
         LR     R3,R6              d
         MH     R3,=H'10'
         AR     R2,R3
         LR     R3,R7              q
         MH     R3,=H'25'
         AR     R2,R3              s=p+n*5+d*10+q*25
         C      R2,=F'100'         if s=100
         BNE    NOTOK
         LA     R1,1(R1)           count=count+1
NOTOK    LA     R7,1(R7)           q=q+1
         B      LOOPQ
ELOOPQ   LA     R6,1(R6)           d=d+1
         B      LOOPD
ELOOPD   LA     R5,1(R5)           n=n+1
         B      LOOPN
ELOOPN   LA     R4,1(R4)           p=p+1
         B      LOOPP
ELOOPP   XDECO  R1,PG+0            edit count
         XPRNT  PG,12              print count
         XR     R15,R15
         BR     R14
AMOUNT   DC     F'100'             start value in cents
PG       DS     CL12
         YREGS
         END    COINS