小P的故事——神奇的换零钱

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

已知A国经济很落后,他们只有1、2、3元三种面值的硬币,有一天小P要去A国旅行,想换一些零钱,小P很想知道将钱N兑换成硬币有很多种兑法,但是可惜的是他的数学竟然是体育老师教的,所以他不会啊、、、他只好求助于你,你可以帮他解决吗?

提示:输入数据大于32000组。

Input

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

Output

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

Sample Input

100 
1500

Sample Output

884 
188251

Hint

 

Source

xfl