题目描述

小 $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,3$ 、 $2,3,4$ 、 $1,2,3,4$ 放苹果不满足题意，所以一共有 $16-3=13$ 种方案。

数据规模

$70\%$ 的数据， $n≤20$ 。

$100\%$ 的数据， $n≤1000$ 。