Q674: Coin Change

給你一個金額（ n cents），請你回答共有多少種硬幣組合的方式。例如：n=11，那麼你可以有以下4種硬幣的組合：

1. 1個 10 cent的硬幣加上1個 1 cent的硬幣
2. 2個 5 cent的硬幣加上1個 1 cent的硬幣
3. 1個 5 cent的硬幣加上6個 1 cent的硬幣
4. 11個 1 cent的硬幣

p.s 美國的零錢共有以下5種硬幣以及其面值：

• penny, 1 cent
• nickel, 5 cents
• dime, 10 cents
• quarter, 25 cents
• half-dollar, 50 cents

請注意：n=0 我們算他是有一種方式。

Input

每組測試資料1列，有1個整數n（0 <= n <= 7489），代表零錢的總金額（單位：cent）。

Output

對每組測試資料請輸出共有多少種硬幣組合方式。

Sample input

0
17 
11
4
1000
2000
7489

Sample Output

1
6
4
1
801451
11712101
2146113925