100610 : 数列的第n项
Description

求数列的第n项：

a_1=0

a_2=1

a_3=1

a_4=a_1+2*a_2+a_3

a_5=a_2+2*a_3+a_4

……

Input

一行，一个正整数表示n。

对于100%的数据：

1\le n \le 50 。

Output

一行，一个整数表示第n项的值。

Examples

Input

6

Output

13
Language：
Theme：
登录以提交代码;