题目描述

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

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

由于方案数可能很多，所以你只需要方案个数 % 55555 就可以了。

输入格式

一个正整数，即 n 。

数据规模

70% 的数据，n ≤ 20

100% 的数据，n ≤ 1000

输出格式

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

样例

4

13

样例解释

一共有 4 个格子，每个格子可以选择放或者不放，因此根据乘法原理共有 2*2*2*2 = 16 种方案，其中在（ 1，2，3 ）上放炸弹是不合法的，会炸死小头。同样（ 2，3，4 ）和（ 1，2，3，4 ）也都不合法，所以一共有 16 - 3 = 13 种方案 13 % 55555 = 13 ，因此答案为 13