说明

时间限制：1 Sec 内存限制：512 MB 输入文件：seq.in 输出文件：seq.out

给定整数 $N$。定义数列 $a$：$a_0=1$，$a_i = a_{\lfloor i/3 \rfloor} + a_{\lfloor i/5 \rfloor}$。请求出数列第 $N$ 项 $a_N$。

其中对于大于等于 $0$ 的实数 $x$，$\lfloor x \rfloor$ 代表对 $x$ 向下取整。

输入格式

第一行一个整数 $N$。

输出格式

输出一行，为 $a_N$。

样例

样例 1

7

4

样例说明：

$a_7 = a_{\lfloor 7/3 \rfloor} + a_{\lfloor 7/5 \rfloor} = a_1 + a_2 = (a_{\lfloor 1/3 \rfloor} + a_{\lfloor 1/5 \rfloor}) + (a_{\lfloor 2/3 \rfloor} + a_{\lfloor 2/5 \rfloor}) = (a_0 + a_0) + (a_0 + a_0) = (1 + 1) + (1 + 1) = 4$

样例 2

1000000000000000000

3207281389

数据范围

对于 30% 的数据，$N \le 10$。

对于 100% 的数据，$0 \le N \le 10^{18}$。