Description

在一个国家仅有1分，2分，3分硬币，将钱N兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法

Input

每行只有一个正整数N，N小于32768

Output

对应每个输入，输出兑换方法数

Sample Input

2934 
12553

Sample Output

718831 
13137761 

HINT

Source