Handshakes

The meeting is over, and it is time to shake hands. Everyone is seated in a single row along one side of a rectangular table.

Each person may shake hands with the person immediately to their left or immediately to their right, or with no one at all. A single handshake always happens between two neighboring people, and no person can take part in more than one handshake at the same time.

Count how many different ways the group can shake hands without anyone leaving their seat. (The case where nobody shakes hands counts as one way.)

The first line contains the number of people at the meeting, $n$ ($1 \le n \le 10^7$).

Print the number of ways to shake hands. Because this value can become very large, print only its last digit (the ones digit).

When $n = 4$ there are 5 possible ways: nobody shakes hands; only (1,2) shake; only (2,3) shake; only (3,4) shake; or (1,2) and (3,4) shake at the same time. Here (i, j) means the $i$-th and $j$-th people from the left shake hands with each other.