Informatica Online Judge

  Graph Counting 2 [1286 / 0506]

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


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

[koistudy.net (32nd 이국렬)]

Background

이번에는 쿠쿨이가 안형서에게 n개의 정점과 방향이 있는 간선으로 연결된다. 이전과 다르게 규칙이 좀더 까다로워졌다.



* 정점 i에서 출발해서 정점 i로 도착하는 간선은 6개 까지 존재할 수 있다.
* 정점 i에서 출발해서 정점 j로 도착하는 간선이 3개 까지 존재할 수 있다.
* 정점 i에서 출발하거나 도착하는 간선이 하나도 없어도 된다.

이 때, 형서가 만들 수 있는 그래프의 경우의 수를 출력하여라.

Input

정점의 수 n이 주어진다.

[입력값의 정의역]
1 <= n <= 5000000

[Sub-Task Info]
#1 : n <= 500,000
#2 : n <= 500,000,000

Output

만들 수 있는 그래프의 개수를 출력하여라. 수가 클 수 있으니 1,000,000,007 로 나눈 나머지를 출력한다.

IO Example

입력
2

출력
784

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