100610 - 数列的第n项

求数列的第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

……

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

对于100%的数据：

1\le n \le 50 。

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