题目描述

小明想知道，满足以下条件的正整数序列的数量：

1. 第一项为 n；
2. 第二项不超过 n；
3. 从第三项开始，每一项小于前两项的差的绝对值。 请计算，对于给定的 n，有多少种满足条件的序列。

输入格式

多行输入，读到文件尾截止 每行输入一个整数N 对于所有评测用例，1

输出格式

每行输出一个整数，表示答案。答案可能很大， 请输出答案除以10000的余数。 对于样例4，以下是满足条件的序列： 4 1 4 1 1 4 1 2 4 2 4 2 1 4 3 4 4

1
2
3
4
5
6
7
8
9
10
20
30

1
2
4
7
14
26
53
106
220
452
3277
3556

提示

题目数据由计算1801郭程提供