问题描述

小 $A$ 的班级准备开班会。 班级有 $N$ 个连续座位，编号为 $1 \sim N$，老师让小 $A$ 给大家准备苹果。 小 $A$ 考虑到有人喜欢苹果，有人不喜欢，因此他会在 $1 \sim N$ 的每个座位放最多 $1$ 个苹果，他不会在连续的 $3$ 个座位上都放苹果。请编程计算出，小 $A$ 有多少种不同的放苹果的方案。 请注意：一个也不放也是一种方案，由于方案数可能很多，所以你只需要输出方案数 $\mod 55555$ 就可以了。

输入格式

一个正整数，即 $n$ 。

输出格式

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

数据范围

样例 $1$ 的解释 一共有 $4$ 个座位，每个座位可以选择放或者不放，因此根据乘法原理共有 $2 \times 2 \times 2 \times 2=16$ 种方案，其中在 $1,2,3$、$2,3,4$、$1,2,3,4$ 放苹果不满足题意，所以一共有 $16-3=13$ 种方案。 数据规模 $70\%$ 的数据，$n≤20$。 $100\%$ 的数据，$n≤1000$。

样例

输入 #1

4

输出 #1

13

输入 #2

100

输出 #2

10596