上台阶

小瓜想走上一个一共有n级的台阶，由于小瓜的腿长比较特殊，他一次只能向上走1级或者3级或者5级台阶。小瓜想知道他有多少种方法走上这n级台阶，你能帮帮他吗？#

输入

一行一个整数n（n<=100000），表示一共有n级台阶。#

输出

一行一个整数，表示小瓜上台阶的方案数对100003取余的结果。#

样例输入

3

样例输出

2