下楼梯的和尚

题目描述

从前有座山，山里有座庙，庙里有个老和尚Island Close和小和尚 ~~~o(∩_∩)o~~~
一天，Island Close闲来无事，准备靠走下庙前面的楼梯来强身健体~！ 0w0
Island Close一步可以向下走一个或两个或三个台阶 //我不会告诉你他一次向下走4个台阶会拉伤的0w0
Island Close想看看他能下去的方法一共有多少种，//这句和上一句是重点。。。
于是他就下了一次两次三次然后就累了，然后就请小和尚来帮忙了//再一次躺枪了！！！
小和尚很懒，他才不想一次一次下楼梯呢。。。TAT*2
于是怎么做才能得到老和尚想要的答案呢？

输入

多组测试数据。 每组测试数据为一行，包含一个整数n（0<n<100000），表示台阶总数;

输出

对于每组测试数据，输出一行，包含一个整数，表示方法一共有多少种。 结果请对12211060取模~~~0w0~~~

输入样例

1
2
3

输出样例

1
2
4