题目描述

小蔡决定在小头家门口安放炸弹！

小头家门口有 $n$ 个连续的格子排成一行，对于每个格子，小蔡可以决定放一颗炸弹或者不放。为了防止小头被炸死，小蔡不会在连续 $3$ 个格子都放上炸弹。小蔡想知道一共有多少种安放炸弹的方案（可以一个也不放）。

由于方案数可能很多，所以你只需要输出方案数对 $55555$ 取模的结果。

输入格式

一行，一个正整数 $n$。

输出格式

一行，一个整数，表示方案数模 $55555$ 后的结果。

样例

4

13

样例解释
$n=4$ 时，每个格子可以放或不放，根据乘法原理共有 $2^4=16$ 种方案。其中在格子 $(1,2,3)$ 上都放炸弹是不合法的，同样 $(2,3,4)$ 和 $(1,2,3,4)$ 也都不合法，所以合法方案共有 $16-3=13$ 种。$13 \bmod 55555 = 13$，因此答案为 $13$。

数据范围与提示

• 对于 $70\%$ 的数据：$n \le 20$。
• 对于 $100\%$ 的数据：$n \le 1000$。