题目背景

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

题目描述

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

任务：给定N，求三角形1~N的基的最大值 再去 mod 10007。

输入格式

一个整数N

输出格式

一个整数，表示1~N构成的三角形的最大的“基”

4

24

1125

700

提示

数据：

20% 0<=N<=100

50% 0<=N<=3000

100% 0<=N<=1000000

样例解释：

1 3 4 2

4 7 6

11 13

24 是N=4的时候的最大值，当然还有别的构成形式。

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

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

不要面向数据编程！