珅泽教育的算法实验室里有一块数列显示屏。刘老师把一组“三连递推数”写进了控制程序：第 $1$ 项和第 $2$ 项都是 $0$，第 $3$ 项是 $1$；从第 $4$ 项开始，每一项都等于它前面连续三项之和。

显示屏需要支持很大的项数。为了让屏幕上的数字保持在固定范围内，每次得到新的数值后都只保留它除以 $10007$ 的余数。小泽输入项号 $N$ 后，屏幕上出现的正是第 $N$ 项经过上述处理后的数值。

输入格式

一行一个整数 $N$，表示需要查看的项号。

输出格式

一行一个整数，表示数列第 $N$ 项除以 $10007$ 的余数。

7

7

1

0

100000

7927

样例解释

前七项依次为 $0,0,1,1,2,4,7$，所以第 $7$ 项为 $7$。

数据范围与约定

• $1\le N\le100000$