← 返回题目
题库练习 【蓝桥杯】【国赛】特殊整数序列方案
← 上一题 下一题 →

A3738 | 【蓝桥杯】【国赛】特殊整数序列方案

来源蓝桥杯
时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

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

1. 第一项为 n；

2. 第二项不超过 n；

3. 从第三项开始，每一项小于前两项的差的绝对值。


请计算，对于给定的 n，有多少种满足条件的序列。

输入格式

输入一行包含一个整数 n。

输出格式

输出一个整数，表示答案。答案可能很大，请输出答案除以10000的余数。

以下是满足条件的序列：

4 1
4 1 1
4 1 2
4 2
4 2 1
4 3
4 4

输入输出样例

输入 #1
4
输出 #1
7
C++ 编辑器
输入
输出