DNA序列

题目描述

在 $X$ 国中，所有的物种基因都是由 $0$ 和 $1$ 组成的长度为 $L$ 的字符串，但是如果这个字符串中包含“ $101$ ”和“ $111$ ”的子串，就会感染病毒。作为 $X$ 国的生物学基因专家，他想知道针对长度为 $L$ 的基因里，有多少种不会感染病毒的基因？ 例如，$L=4$ 的时候，不会感染病毒的基因是：0000、0001、0010、0100、1000、0011、0110、1100、1001，答案是 $9$。

输入格式

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

输出格式

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

4

9

提示

（暂无提示）

来源

童程童美