该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

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

Format

Input

每行输入一个不超过1e10的非负整数n。

Output

每行输出兑换的方法数。

Samples

1
2934

1
718831

Limitation

1s, 1024KiB for each test case.