Deild Goðsagnanna

Competitive Programming Association of Iceland의 구성원들은 League of Legends을 상당히 많이 플레이한다. League of Legends에서는 파랑 팀과 빨강 팀이라는 두 팀이 있으며, 각 팀은 다섯 명의 플레이어로 구성된다. 각 플레이어는 경기가 시작되기 전에 플레이할 수 있는 챔피언 중 하나를 선택하며, 어떤 두 플레이어도 같은 챔피언을 선택할 수 없다.

각 챔피언에게는 약점과 강점이 있으므로, 팀원들의 챔피언과 잘 어울리고 상대 팀의 챔피언을 상대하기에 적합한 챔피언을 선택하는 것이 중요하다. 따라서 챔피언을 현명하게 선택하는 것이 매우 중요하다. 상대가 특정 챔피언을 선택하지 못하게 하기 위해 각 팀은 여러 챔피언을 선택 금지할 수 있다. 챔피언을 선택 금지하면 어느 팀도 그 챔피언을 선택할 수 없다.

드래프트 과정은 다음 단계로 이루어진다:

• 파랑 팀이 챔피언 하나를 선택 금지한다.

• 빨강 팀이 챔피언 하나를 선택 금지한다.

• 파랑 팀이 챔피언 하나를 선택 금지한다.

• 빨강 팀이 챔피언 하나를 선택 금지한다.

• 파랑 팀이 챔피언 하나를 선택 금지한다.

• 빨강 팀이 챔피언 하나를 선택 금지한다.

• 파랑 팀이 챔피언 하나를 선택한다.

• 빨강 팀이 챔피언 둘을 연속으로 선택한다.

• 파랑 팀이 챔피언 둘을 연속으로 선택한다.

• 빨강 팀이 챔피언 하나를 선택한다.

• 빨강 팀이 챔피언 하나를 선택 금지한다.

• 파랑 팀이 챔피언 하나를 선택 금지한다.

• 빨강 팀이 챔피언 하나를 선택 금지한다.

• 파랑 팀이 챔피언 하나를 선택 금지한다.

• 빨강 팀이 챔피언 하나를 선택한다.

• 파랑 팀이 챔피언 둘을 연속으로 선택한다.

• 빨강 팀이 챔피언 하나를 선택한다.

원래 선택할 수 있는 챔피언은 $20$개뿐이었다. (실제로 원래 챔피언은 $17$개였지만, 당시 드래프트 과정에는 $16$개의 챔피언만 필요했다.) 하지만 게임 개발자들은 계속해서 더 많은 챔피언을 추가하고 있다. 두 드래프트의 단계 중 어느 하나라도 다르면 두 드래프트가 다르다고 한다. 현재 선택할 수 있는 챔피언은 $n$개이다. 서로 다른 드래프트 과정은 몇 개 존재하는가?

각 챔피언이 어느 단계에서 선택되거나 선택 금지되는지만 중요하다는 점에 유의한다.

아래에는 팀들이 챔피언을 선택한 세 가지 드래프트 과정을 나타내는 세 개의 이미지가 있다. 파랑 팀은 왼쪽에 있고 빨강 팀은 오른쪽에 있다. 선택 금지된 챔피언은 왼쪽에서 오른쪽 순서로 나타난다. 선택된 챔피언은 위에서 아래 순서로 나타난다.

[h!]

챔피언들이 선택 금지되고 선택된 드래프트 과정의 예시.

위 드래프트 과정에서는 다음과 같은 일이 일어난다:

• 파랑 팀 선택 금지: Fizz.

• 빨강 팀 선택 금지: Rumble.

• 파랑 팀 선택 금지: Skarner.

• 빨강 팀 선택 금지: Ekko.

• 파랑 팀 선택 금지: Nami.

• 빨강 팀 선택 금지: Olaf.

• 파랑 팀 선택: Jarvan IV.

• 빨강 팀 선택: Kindred.

• 빨강 팀 선택: Lux.

• 파랑 팀 선택: Brand.

• 파랑 팀 선택: Tryndamere.

• 빨강 팀 선택: Rammus.

• 빨강 팀 선택 금지: Twitch.

• 파랑 팀 선택 금지: Twisted Fate.

• 빨강 팀 선택 금지: Malphite.

• 파랑 팀 선택 금지: Vladimir.

• 빨강 팀 선택: Jinx.

• 파랑 팀 선택: Draven.

• 파랑 팀 선택: Sett.

• 빨강 팀 선택: Blitzcrank.

[h!]

이 드래프트 과정은 이전 드래프트 과정과 동등하다.

위 드래프트 과정에서는 파랑 팀이 Brand를 선택하기 전에 Tryndamere를 선택한다는 점을 제외하면 이전 드래프트 과정과 같은 일이 일어난다. 그럼에도 두 선택은 같은 단계에서 이루어지므로 두 드래프트 과정은 동등하다.

[h!]

이 드래프트 과정은 앞의 두 드래프트 과정과 다르다.

위 드래프트 과정에서는 빨강 팀이 Lux를 선택하기 전에 Rammus를 선택한다는 점을 제외하면 첫 번째 드래프트 과정과 같은 일이 일어난다. 이 선택들은 서로 다른 단계에서 이루어지므로, 이 드래프트 과정은 앞의 두 과정과 다르다.

채점

그룹 | 점수 | 제약 조건

1 | 30 | $20 \leq n \leq 21$

2 | 25 | $20 \leq n \leq 100$

3 | 20 | $20 \leq n \leq 10^{6}$

4 | 15 | $20 \leq n \leq 10^{9}$

5 | 10 | $20 \leq n \leq 10^{18}$

입력은 게임에서 선택할 수 있는 서로 다른 챔피언의 수를 나타내는 정수 $n$ 하나를 포함하는 한 줄로 이루어진다.

서로 다른 드래프트 과정의 수가 정수 $k$라고 하자. $k$은 매우 큰 수일 수 있음에 유의한다. 따라서 $k$을 $1\,000\,000\,007$로 나눈 나머지를 나타내는 정수 하나를 한 줄에 출력한다.