시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB109676264.583%

문제

가희는 클럽 오디션 모드 중 $8$키 일반 모드를 하고 있습니다. 이 모드에서는 키 노트가 여러 개 등장합니다. 레벨이 $lv$인 키 노트에는 방향키가 $lv$개 등장합니다. 플레이어는 역방향 모드 $1$부터 $6$까지, 그리고 랜덤 이렇게 $7$개의 모드를 선택할 수 있습니다. 키 노트의 레벨에 따라, 등장하는 방향키의 종류가 다릅니다.

  • $lv$이 $5$ 이하인 경우
    • 상, 하, 좌, 우 $4$개의 방향키만 등장합니다.
  • $lv$이 $6$ 이상인 경우
    • 상, 하, 좌, 우, 우상, 우하, 좌상, 좌하의 $8$개의 정방향 키가 등장할 수 있습니다.
    • 8개의 정방향 키에 대한 역방향 키도 등장할 수 있습니다.
    • 역방향 키 모드가 $c$일 때, 키 노트에 $c$개의 역방향 키가 등장합니다. 만약, 역방향 키 모드가 랜덤이라면 역방향 키는 키 노트에 최대 $6$개까지 등장합니다.

가희가 역방향 키 모드를 랜덤으로 선택했을 때, 레벨이 $lv$인 키 노트의 패턴 수를 $10^{9} + 7$로 나눈 나머지를 출력해 주세요.

입력

첫 번째 줄에 키 노트의 레벨 $lv$이 주어집니다.

출력

문제의 정답을 출력해 주세요.

제한

  • $1 ≤ lv ≤ 50\,000$

예제 입력 1

6

예제 출력 1

16777216

[그림 1] 가능한 패턴 중 $2$가지

노란색은 역방향키를, 회색은 정방향 방향키를 의미합니다. 위 $2$개의 키 노트는 우, 우하, 좌하, 우, 우상, 하로 동일합니다. 하지만 $5$번째 방향키가 위의 키 노트는 역방향 좌하, 아래의 키 노트는 우상으로 다릅니다. 따라서 다른 패턴으로 취급합니다.

예제 입력 2

43985

예제 출력 2

979440029