测试数据来自 nnu_contest/5c1df431f413627097c4aa43

这一天，小明和小璐正在上楼，他突然停了下来。小璐问他：何事？小明说：我有三种步伐：1个台阶/步，2个台阶、3个台阶。从1楼到2楼有n级台阶。我正在思考，有多少种不同的走法。
小璐说：这个问题，你早就解决了，还想什么？
小明说：每当我走了一步3个台阶后，就有点累，下一步就只能走一步1个台阶了。增加了这个约束条件后，有多少种不同的走法呢？
小璐说：看来上个楼，也不容易啊!
输入一行，一个整数n，n<30，表示台阶数。
输出一行，一个整数，表示不同走法的个数。

测试案例1：
输入

4

输出

7

测试案例2：
输入

5

输出

12