题目描述

一个1 * n 的方格图形（宽为1，长为n，共n个方格）用黑、白两种颜色填涂每个方格。如果每个方格只能填涂一种颜色，且不允许两个黑格相邻，我们求解一共有多少种涂色方案？（n ≤ 20）

输入格式

一个整数n，表示方格图形长度

输出格式

输出1 * n的方格的涂色方案总数

输入样例#1

2

输出样例#1

3