1857: 【编程进阶】臻臻跨天梯
Memory Limit：16 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：22
Solved：3
Description
”能共你 沿途来爬天梯 黑夜亦亮丽～“
”问我亦无愧 有你可以 拆破这天际～“
一首c~ALL STAR的《天梯》，是臻臻最喜爱的歌曲之一。没事的时候他喜欢自己唱几句。
如果真有天梯，臻臻会怎样跨上顶峰呢？
臻臻爬天梯，他不按常人出牌，不喜欢一步走1级，他可以爬2级、3级。
臻臻很可爱，每到一处楼梯处，他都想知道直完这个楼梯有多少种走法。但由于有的时候楼梯级数太多，可能是个天文数字，很显然，对于还处于小学5年级的臻臻是不太现实的。聪明的你，能帮臻臻实现这个愿望吗？
提示：每次只爬2级，或者3级。
Input
多笔测资，每笔测资一行：整数n (1<=n<=3000)
Output
对第笔测资，输出一个整数，为n级楼梯臻臻走完的方法数。
Sample Input Copy
3
4
5
6
7
100
1000
3000Sample Output Copy
1
1
2
2
3
670976837021
54674979116979634644334044682461040929989120352560878128951396303355699209053903787739616124344673415685123376094847686722
965240441988114589000715950343307480004197433009736768870794955651754169649685869470993606506856952861537341136353103329255342755679697611145672189600895191722236619577504327138773023630589524307830626115337396876283076030885415988248703963933340545867504816035141961774832836103230903802976260084017890759842890836692892902018239722631236245822608440081125729600001