《瞿葩的数字游戏》T3-三角圣地

题目背景

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

题目描述

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

输入输出格式

输入格式


一个整数N

输出格式


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

输入输出样例

输入样例 #1

4

输出样例 #1

24

输入样例 #2

1125

输出样例 #2

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:它叫做三角圣地,其实它就是个三角形~ 本题数据已经更新,目前全部正确无误! 不要面向数据编程!