（题目太瘆人了）

题目背景

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

题目描述

不是说三角形是最稳定的图形嘛，数字王国的中心便是由一个倒三角构成。这个倒三角的顶端有一排数字，分别是 $1 \sim N$。$1 \sim N$ 可以交换位置。之后的每一行的数字都是上一行相邻两个数字相加得到的。这样下来，最底端就是一个比较大的数字啦！数字王国称这个数字为「基」。国王 $1$ 希望「基」越大越好，可是每次都自己去做加法太繁琐了，他希望你能帮他通过编程计算出这个数的最大值。但是这个值可能很大，所以请你把结果 $\bmod\ 10007$。

任务：给定 $N$，求三角形 $1 \sim N$ 的基的最大值 $\bmod\ 10007$ 的结果

输入格式

一行一个数，$N$，表示三角形的大小。

输出格式

一个整数，表示 $1 \sim N$ 大小的三角形构成的最大的「基」。

提示

【样例解释】

$1\ \ \ \ 3\ \ \ \ 4\ \ \ \ 2$

$4\ \ \ \ 7\ \ \ \ 6$

$11\ \ \ 13$

$24$

「基」为 $24$ 是 $N = 4$ 时的最大值，当然还有别的构成形式。

【数据范围】

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

对于 $50\%$ 的数据，$0 \le n \le 3 \times 10^3$。

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

PS：它叫做三角圣地，其实它就是个三角形~

本题数据已经更新，目前全部正确无误！

不要面向数据编程！

### 题目背景

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

### 题目描述

不是说三角形是最稳定的图形嘛，数字王国的中心便是由一个倒三角构成。这个倒三角的顶端有一排数字，分别是 $1 \sim N$。$1 \sim N$ 可以交换位置。之后的每一行的数字都是上一行相邻两个数字相加得到的。这样下来，最底端就是一个比较大的数字啦！数字王国称这个数字为「基」。国王 $1$ 希望「基」越大越好，可是每次都自己去做加法太繁琐了，他希望你能帮他通过编程计算出这个数的最大值。但是这个值可能很大，所以请你把结果 $\bmod\  10007$。

任务：给定 $N$，求三角形 $1 \sim N$ 的基的最大值 $\bmod\ 10007$ 的结果

### 输入格式

一行一个数，$N$，表示三角形的大小。

### 输出格式

一个整数，表示 $1 \sim N$ 大小的三角形构成的最大的「基」。

### 提示

【样例解释】

$1\ \ \ \ 3\ \ \ \ 4\ \ \ \ 2$

$4\ \ \ \ 7\ \ \ \ 6$

$11\ \ \ 13$

$24$

「基」为 $24$ 是 $N = 4$ 时的最大值，当然还有别的构成形式。

【数据范围】

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

对于 $50\%$ 的数据，$0 \le n \le 3 \times 10^3$。

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

PS：它叫做三角圣地，其实它就是个三角形~

本题数据已经更新，目前全部正确无误！

不要面向数据编程！