원탁의 악수

$n$명이 원탁에 둘러앉아 있습니다. 각 사람은 자기 바로 양옆에 앉은 두 이웃 중 한 명하고만 악수할 수 있고, 아무와도 악수하지 않아도 됩니다. 한 사람이 악수에 참여하는 횟수는 최대 한 번입니다(같은 사람의 손이 두 번 쓰일 수 없습니다).

자리를 옮기지 않고 악수를 배치하는 서로 다른 방법이 몇 가지인지 구하세요. 아무도 악수하지 않는 경우도 한 가지 방법으로 셉니다.

이 수가 매우 커질 수 있으므로, 방법의 수를 $10$으로 나눈 나머지, 즉 마지막 한 자리 숫자만 출력합니다.

첫 줄에 사람 수를 나타내는 정수 $n$ ($3 \le n \le 2000000000$)이 주어집니다.

악수를 배치하는 방법의 수의 마지막 한 자리 숫자를 한 줄에 출력합니다.

악수하는 모든 경우입니다.