有一個國家叫「方塊國」，方塊國使用「方塊幣」當作流通的貨幣，這種貨幣是由方塊所組成，其面額是 1 ~ 21 的立方倍，也就是 $1,8,27,\cdots{},9261$。
你的任務是要計算用方塊幣付款的所有可能方式，例如付 21 元共有三種付款方式：
- 付 21 個 1 元方塊幣
- 付 1 個 8 元方塊幣加 13 個 1 元方塊幣
- 付 2 個 8 元方塊幣加 5 個一元方塊幣。
輸入的每一列會有一個整數，請你計算此金額的所有可能付款方式，此金額大小介於 1 ~ 10000 之間。
Sample input
10
21
77
9999
Output for sample input
2
3
22
440022018293