【递归入门】炸弹安放
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
Description
小蔡决定在小头家门口安放炸弹！！ 小头家门口有n个连续的格子排成一行，对于每个格子，小蔡可以决定放一颗炸弹或者不放。为了防止小头被炸死，小蔡不会在连续3个格子都放上炸弹。小蔡想知道一共有多少安放炸弹的方案(可以一个也不放)。 由于方案数可能很多，所以你只需要方案个数mod 55555就可以了。Input Format
一个正整数，即nOutput Format
仅包含一个整数，即答案413