题目描述

源老师由于步子迈的比较大，最多可以一次上 $3$ 阶楼梯，当然他也可以选择上一阶或者两阶。

现再问你上 $n$ 阶楼梯一共有多少种方法，由于答案可能很大，你只需要输出最终数字对 $100003$ 取余的结果。

输入格式

第一行输入一个 $n$

输出格式

输出一个数字

5

13

提示

对于$50\%$的数据，$1\leq n\leq 20$

对于$100\%$的数据，$1\leq n\leq 2*10^4$