小 A 的班级准备开班会。

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

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

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

输入

一个正整数，即 n 。

输出

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

4

13

100

10596

样例 1的解释

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

数据规模

70% 的数据，n≤20。

100% 的数据，n≤1000。