가희와 클럽 오디션 3

가희는 클럽 오디션 모드 중 $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$