描述

最近ZSY刚刚学会DFS!ZSY正在用DFS遍历一棵有根树。但2B的ZSY竟然还不满足于仅仅遍历一棵树,ZSY还想知道对于一颗N个节点的有根树的DFS序列,可能对应着多少种有根树?但SB的ZSY只知道N <= 3的情况,聪明的你能不能帮助ZSY求出其它情况中树的种数对10007取模的值呢?

输入格式

一个整数N。

输出格式

一个整数,表示N个节点的有根树的DFS序列可能对应着的有根树的种数对10007取模的值。

样例输入

3

样例输出

2

数据范围与约定

对于100%的数据,1 <= N <= 1018

样例解释

不妨设DFS序列为1, 2, 3。有两种可能的有根树,即1的左儿子、右儿子分别为2、3,或者1的儿子为2、2的儿子为3。

来源

原创