题目描述

上体育课的时候，老师要求同学们4人一组练习传球。

假设有ABCD四个人在练习传球, 一开始球在A处. 每次传球时, 控球的人将球传给除自己以外的任意一个人. 问传球n次后, 球又回到A处的传球路线有多少种?

输入格式

1行，1个整数n(2≤n≤40)。

输出格式

1个整数，表示符合题意的方法数。

输入样例 #1

3

输出样例 #1

6

输入样例 #2

2

输出样例 #2

3

输入样例 #3

4

输出样例 #3

21

提示

6种路线是ABCA,ABDA,ACBA,ACDA,ADBA,ADCA.

数据范围

1行，1个整数n(2≤n≤40)。