题目描述

小珅这人说话不怎么过脑子，经常会说出一些让自己和大家都有尴尬的话。这时候，周围的人往往会好心地给他一个台阶下。但小珅又特别不会顺杆爬，给他下台阶需要一定的技巧，久而久之，他周围的人都练就了一手给台阶的好本领。小珅的朋友们分工合作，算准距离:已知小珅张口就来，此时他离地n级台阶:

朋友 A 负责给1级的台阶

朋友 B 负责给 2 级的台阶;

朋友 C 负责给 3 级的台阶。

四个人唇枪舌战，三个朋友轮流接话，终于缓和尴尬的气氛，众人得以松了一口气。

请问总共有多少种给台阶的方案？

输入格式

输入有一行，第一行一个正整数 n（n<70），表示询问的是给第 n 级台阶;

输出格式

输出一个数字 a，表示给第 n 级台阶的方案数。

输入样例 #1

10

输出样例 #1

274

输入样例 #2

1

输出样例 #2

1

输入样例 #3

2

输出样例 #3

2

数据范围

输入有一行，第一行一个正整数 n（n<70），表示询问的是给第 n 级台阶;