该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述：

在北京的一家生物科技研究院里，年轻的研究员小李正在进行一项关于特殊生物基因序列的研究。在这个虚构的生物体系中，所有生物的基因序列都是由 0 和 1 组成的长度为 L 的字符串。 但最近，研究院发现了一个棘手的问题：如果基因序列中包含 “101” 和 “111” 这样的子串，这种生物就会患上一种神秘的疾病，导致其生理机能紊乱甚至死亡。这一发现让整个研究院都高度紧张起来，因为这关系到对这些生物未来的研究走向以及可能的应用。 小李作为团队中最具创新思维的成员，承担起了一个关键任务：计算出针对长度为 L 的基因序列里，有多少种是不会让生物感染这种神秘疾病的。他深知这个任务的重要性，每天都在实验室里埋头苦算。 例如，当基因序列长度 L = 4 的时候，经过小李的仔细推导，发现不会导致生物患病的基因序列有：0000、0001、0010、0100、1000、0011、0110、1100、1001，一共有 9 种 。随着研究的深入，基因序列长度 L 不断变化，计算的难度也越来越大，小李决定借助计算机编程来解决这个复杂的问题。

输入格式：

一行一个整数 L，表示基因为长度为 L 的 01 字符串，其中3≤L≤90

输出格式：

一行一个整数，输出对应的不会患毒的基因种数。

样例：

4

9