题目背景

国王1带大家到了数字王国的中心：三角圣地。

题目描述

数字王国的中心是由一个倒三角构成。

倒三角一共 $N$ 层，从上往下第 $i$ 层有 $N-i+1$ 个数字。倒三角的第 $1$ 层必须是 $1 \sim N$ 的全排列之一，即必须使用 $1 \sim N$ 之间的所有数字且不能重复。从第 $2$ 层开始以后每一层的数字都是由其左上方和右上方两个数字相加得到的。例如，下面是一个合法的倒三角形：

1   2   3   4
  3   5   7
    8   12
      20

这个倒三角形的 $N$ 为 $4$，其最后一层的数字为 $20$。

数字王国称最后一层的数字为“基”，请你编程求出“基”的最大值对 $10007$ 取模的结果。

输入格式

一行，一个整数 $N$，表示倒三角的层数。

输出格式

一行一个整数，表示 $N$ 层倒三角“基”的最大值对 $10007$ 取模的结果。

4

24

1125

700

提示

样例解释

一种可行的方案为：

1   3   4   2
  4   7   6
    11  13
      24

可以证明没有比这更好的方法。

数据范围

对于 $20\%$ 的数据，$N \le 100$。

对于 $50\%$ 的数据，$N \le 3000$。

对于 $100\%$ 的数据，$0 \le N \le {10}^6$。