악수

회의가 끝나고, 이제 악수를 나눌 시간이다. 모든 사람은 직사각형 탁자의 한 변에 일렬로 앉아 있다.

각 사람은 바로 왼쪽 또는 바로 오른쪽에 앉은 사람과 악수할 수 있고, 아무와도 악수하지 않아도 된다. 한 번의 악수는 반드시 이웃한 두 사람 사이에서만 이루어지며, 한 사람이 동시에 두 번 이상의 악수에 참여할 수는 없다.

자리에서 일어나지 않고 악수를 나누는 방법이 모두 몇 가지인지 구하여라. (아무도 악수하지 않는 경우도 한 가지 방법으로 센다.)

첫째 줄에 회의에 참석한 사람의 수 $n$ ($1 \le n \le 10^7$)이 주어진다.

첫째 줄에 악수를 나누는 방법의 수를 출력한다. 이 값은 매우 커질 수 있으므로, 방법의 수의 마지막 한 자리(일의 자리)만 출력한다.

$n = 4$일 때 가능한 방법은 다음과 같이 5가지이다: 아무도 악수하지 않기, (1,2)만 악수, (2,3)만 악수, (3,4)만 악수, (1,2)와 (3,4)가 동시에 악수. 여기서 (i, j)는 왼쪽에서 $i$번째와 $j$번째 사람이 서로 악수함을 뜻한다.