Sum

Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

给出无限长的序列1,1,3,1,3,5,7,1,3,5,7,9,11,13,15,1,3,5,7,9...,问对于序列的前N个数,所有的连续上升子序列的和是多少.
如N = 6的时候,序列是{1,1,3,1,3,5},它的所有连续上升子序列是{1},{1},{1,3},{3},{1},{1,3},{1,3,5},{3},{3,5},{5},结果为39.

Input

N <= 10^9

Output

对于每个N,将结果 % 10007输出

Sample Input

1
2
6

Sample Output

1
2
39

Hint

总数据<=1000组

注意啊,数是

1

1 3

1 3 5 7

1 3 5 7 9 11 13 15

这样叠起来的。

最后一个提示,

(A / B) % prime_number c = A * inv(B) % prime_number c, inv(B) 的意思是 B * inv(B) % prime_number c = 1

Source

dream

Manager

Information
Solved Number26
Submit Number95
Problem Tags
brute force
math
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel