Informatica Online Judge

  타원의 분할 [1309 / 051D]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 45   Total Tried : 76


The Champion of this Problem (C++) : gs16109 - 0ms / 96byte
My Best Submission (C++) : N/A

[Programming Challenges 110602 modify]

Background

하나의 타원이 주어진다.

그리고 타원의 원주상에 적당히 n개의 점을 찍는다.

n개의 모든 점에 대해서 가능한 선분을 긋는다.

다음 그림은 4개의 점이 있을 경우 선분으로 모든 점을 연결한 것이다.



위 그림과 같이 점이 4개일 경우는 8개의 면이 생긴다.

단 선분을 연결할 때에는 최대한 많은 면이 생길 수 있도록 처음에 점의 위치를 정해야 한다.

원주상에 설정할 점의 수 n을 입력받아서 선분을 그을 때, 생기는 면의 수를 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 점의 수 n이 입력된다.

[입력값의 정의역]
1 <= n <= 100,000

Output

선분에 의해 생기는 면의 수를 출력한다.

단, 면의 수가 너무 많아지기 때문에 1,000,000,007로 나눈 나머지를 출력한다.

IO Example

입력1
2

출력1
2

입력2
4

출력2
8

* 설명 : 입력2의 경우는 위 그림의 예이다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]