가희와 클럽 오디션 3

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

• $lv$이 5 이하인 경우

  • 상, 하, 좌, 우 4개의 방향키만 등장합니다.

• $lv$이 6 이상인 경우

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

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

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

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

• $1 \le lv \le 50\,000$