原題來自：AHOI 2012
暑假期間，小龍報名了一個模擬野外生存作戰(zhàn)訓(xùn)練班來鍛煉體魄，訓(xùn)練的第一個晚上，教官就給他們出了個難題。由于地上露營濕氣重，必須選擇在高處的樹屋露營。小龍分配的樹屋建立在一顆高度為 N+1 尺的大樹上，正當(dāng)他發(fā)愁怎么爬上去的時候，發(fā)現(xiàn)旁邊堆滿了一些空心四方鋼材（如圖 1.1），經(jīng)過觀察和測量，這些鋼材截面的寬和高大小不一，但都是 1 尺的整數(shù)倍，教官命令隊員們每人選取 N 個空心鋼材來搭建一個總高度為 N 尺的階梯來進入樹屋，該階梯每一步臺階的高度為 1 尺，寬度也為 1 尺。如果這些鋼材有各種尺寸，且每種尺寸數(shù)量充足，那么小龍可以有多少種搭建方法？

注：為了避免夜里踏空，鋼材空心的一面絕對不可以向上。

3

5

樣例說明

5 種搭建方法如下圖：

數(shù)據(jù)范圍與提示：

對于全部數(shù)據(jù)，1≤N≤500。