白駿-の字形書記(1146)



Dynamic Programming


質問する


N名の学生がいます.これらの学生を以下のように並べます.
1. 맨 앞줄에는 아무나 설 수 있다.
2. 둘째 줄에도 아무나 설 수 있다.
3. 셋째 줄에는 둘째 줄에 서 있는 사람이 첫째 줄에 서 있는 사람보다 클 경우, 둘째 줄에 서 있는 사람보다 작은 사람만이 설 수 있으며, 
둘째 줄에 서 있는 사람이 첫째 줄에 서 있는 사람보다 작을 경우, 둘째 줄에 서 있는 사람보다 큰 사람만이 설 수 있다.
4. 넷째 줄부터는 둘째 줄과 셋째 줄을 비교하는 식으로 해서 N번째의 줄을 서는 사람은 N-2번째 줄과 N-1번째 줄에 서는 사람을 비교해서 세운다.
学生たちが1が一番小さい人、Nが一番大きい人、同じ身長の人がいない場合、5名を設定すれば1-3-2-5-4、3-2-5-1-4などの方法で立てることができます.
問題は、このようにN人の学生を並べた場合、全部でどれだけの状況が発生するかを見つけることだ.

入力


1行目に生徒数N(1≦N≦100)を入力する.

しゅつりょく


最初の行では、出力総数が1000000の残りの部分です.