题目描述

小晓有 $n$ 个小球，每个小球上都有一个数字，不同球上的数字各不相同。小晓想从 $n$ 个小球中任选若干个小球(数量不小于 $2$ )，并将选中的小球分成 $2$ 堆，其中一堆的任意小球上的数字都比另一堆的任何小球上的数字大。请问总共有多少种选取方法？

答案可能会很大，最后答案请输出对 $10007$ 取模的结果。

输入格式

一个正整数 $n$，表示小球的数量 ( $2 \le n \le 2000$ )。

输出格式

一个整数，代表可选取方法的数量。

样例

3

5

样例解释

假设小球编号为 1，2，3，则存在{(1)，(2)}、{(1)，(3)}、{(2)，(3)}、{(1)，(2，3)}、{(1，2)，(3)}共 5 种方案