小 A 的班级准备开班会。
班级有 N 个连续座位，编号为 1 \sim N，老师让小 A 给大家准备苹果。
小 A 考虑到有人喜欢苹果，有人不喜欢，因此他会在 1 \sim N 的每个座位放最多 1 个苹果，他不会在连续的 3 个座位上都放苹果。请编程计算出，小 A 有多少种不同的放苹果的方案。
请注意：一个也不放也是一种方案，由于方案数可能很多，所以你只需要输出方案数 \mod 55555 就可以了。
一个正整数，即 n 。
仅包含一个整数，即答案。
4
13
100
10596
一共有 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。
东方博宜OJ