1689 - 放苹果

题目描述

A 的班级准备开班会。

班级有 N 个连续座位,编号为 1 \sim N,老师让小 A 给大家准备苹果。

A 考虑到有人喜欢苹果,有人不喜欢,因此他会在 1 \sim N 的每个座位放最多 1 个苹果,他不会在连续的 3 个座位上都放苹果。请编程计算出,小 A 有多少种不同的放苹果的方案。

请注意:一个也不放也是一种方案,由于方案数可能很多,所以你只需要输出方案数 \mod 55555 就可以了。

输入

一个正整数,即 n

输出

仅包含一个整数,即答案。

样例

输入

4

输出

13

输入

100

输出

10596
说明

样例 1 的解释

一共有 4 个座位,每个座位可以选择放或者不放,因此根据乘法原理共有 2 \times 2 \times 2 \times 2=16 种方案,其中在 1,2,32,3,41,2,3,4 放苹果不满足题意,所以一共有 16-3=13 种方案。

数据规模

70\% 的数据,n≤20

100\% 的数据,n≤1000

来源

东方博宜OJ

标签
题目参数
时间限制 1 秒
内存限制 256 MB
提交次数 252
通过人数 137
金币数量 1 枚
难度 入门


上一题 下一题