题目背景

桃花山高耸入云，山顶的道观里，小陶道长已经独自枯坐了千载。

这一世，红尘流转，小陶的徒弟再度转世。虽失了前尘记忆，但冥冥之中的血脉与宿缘，依旧指引着他来到了桃花山脚下。

从凡俗的人间到清修的道观，一共有 $N$ 级古旧的石阶。徒弟驻足仰望，石阶没入云雾之中，隐约能嗅到山顶飘来的淡淡桃花酒香。为了寻回那一丝执念，徒弟毅然踏上了长阶。因缘际会之下，他每一步福至心灵，或迈 $1$ 级，或跨 $2$ 级，或腾挪 $3$ 级台阶。

山顶上，小陶拂去衣襟上的落花，睁开双眼，神识早已锁定了那道正一步步坚定登阶的身影。万千步法，皆是因果。小陶拂袖推演，算着徒弟究竟有多少种不同的步法组合，能最终驻足在自己的身前。

题目描述

已知从山脚到小陶所在的道观共有 $N$ 级台阶。徒弟一开始在最底部的第 $0$ 级，每次向上可以迈 $1$ 级、 $2$ 级或 $3$ 级台阶。

请你编写一个程序，帮小陶算出一共有多少种不同的登阶方式，可以刚好到达第 $N$ 级台阶。由于天道无常，命运的轨迹繁复无穷，最终的方式数请对 $100003$ 取模。

输入格式

输入一个正整数 $N(1 \le N \le 10^5)$，代表桃花山的石阶总级数。

输出格式

输出一个正整数 $ans \pmod{100003}$，代表到达第 $N$ 级台阶的不同方式数对 $100003$ 取模后的结果。

输入输出样例 #1

输入 #1

5

输出 #1

13