საშობაო საჩუქრები

დროის ლიმიტი: 1 წმ

მეხსიერების ლიმიტი: 64 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: USACO, 2002/03, DEC, ORANGE


ფერმერ ჯონს უნდა, რომ ნახირისათვის შეიძინოს საშობაო საჩუქრები. მას აქვს 10 აშშ დოლარი (US$10) იმ სათამაშოების შესაძენად, რომელთა ფასები შესაბამისად არის US$5, US$2, US$1, US$1/2, და US$1/4. მას შეუძლია შეიძინოს ორი 5 დოლარიანი სათამაშო და ფული აღარ დარჩება. ასევე, მას შეუძლია შეიძინოს 20 ცალი 1/4 დოლარიანი, ორი ცალი 2 დოლარიანი და ერთი ცალი 1 დოლარიანი სათამაშო და ასე დახარჯოს ფული მთლიანად და ა.შ. ჯონი ცდილობს იანგარიშოს რამდენი სხვადასხვა ვარიანტით შეიძლება დახარჯოს მან თავისი ფული მთლიანად.

დაწერეთ პროგრამა, რომელიც გამოითვლის, რამდენი სხვადასხვა გზით შეიძლება დახარჯოს ჯონმა N (N მთელი რიცხვია 1 <= N <= 150) დოლარი ზემოთ მოცემული ფასების მქონე სათამაშოების შესაძენად.

 

შეტანის ფორმატი:

ერთი სტრიქონი ერთი მთელი რიცხვით: N

 

გამოტანის ფორმატი:

ერთი სტრიქონი ერთი მთელი რიცხვით, რომელიც არის N დოლარის დახარჯვის სხვადასხვა ვარიანტების რაოდენობა.

 




მაგალითები

შესატანი მონაცემები
10 დაკოპირება
გამოსატანი მონაცემები
343 დაკოპირება