题目背景

学校有很多学生。有一天，校长希望所有学生排成一列。

题目描述

他规定女孩不能单独一个人站。换句话说，要么队列中没有女孩，要么并肩站着一个以上的女孩。n = 4的情况（n是孩子的数量）就像
FFFF，FFFM，MFFF，FFMM，MFFM，MMFF，MMMM 此处F代表女孩，M代表男孩。满足校长需要的队列总数为7。您可以编写一个程序来查找n个孩子的队列总数吗？

输入格式

输入一个整数n表示队伍长度

输出格式

输出一个整数表示满足校长要求的排队方式有几种

输入输出样例 #1

输入 #1

4

输出 #1

7

说明/提示

$n<=30$