题目描述

同学排成一排等待圣诞老人发放礼物。礼物有两种，一种是苹果，一种是磁铁。由于磁铁之间有磁力，两个相邻的同学如果拿到的都是磁铁，他们就会被吸在一起而无法分开，苹果则不存在这个问题。圣诞老人想给这一排N个同学每人发一件礼物，同时又要避免相邻两个同学都拿到磁铁的情况，请问他有多少种发放礼物的方案？你可以认为圣诞老人的大礼包中有足够多的苹果和足够多的磁铁，不会发生某种礼物发到后来不够用的情况。

输入格式

仅有一行包含一个自然数N，表示共有N(N<=30)个同学。

输出格式

仅有一行包含一个自然数，表示圣诞老人发放礼物的方案数。

样例数据

input

5

output

13