Arrangement of Blocks

In this problem, you are given n distinct blocks originally arranged in a specific order. Due to a mishap, each block originally at position i can only be placed in one of the positions i-1, i, or i+1 (with the natural restrictions that the block in position 1 cannot go to position 0 and the block in position n cannot go to position n+1). After rearrangement, each position from 1 to n must receive exactly one block. Your task is to compute the number of possible arrangements. Since the answer might be very large, output only the last 8 digits (without any leading zeros).

It can be proven that the number of arrangements follows the recurrence relation:

\( f(1)=1, \quad f(2)=2, \quad f(n)=f(n-1)+f(n-2) \text{ for } n\ge3 \).

This is equivalent to computing \(F(n+1)\) where \(F(1)=1, F(2)=1\) are the classical Fibonacci numbers. You are required to compute \(F(n+1) \bmod 100000000\).

inputFormat

The input consists of a single integer n (1 ≤ n ≤ 10⁹) representing the number of blocks.

outputFormat

Output a single integer: the last 8 digits of the number of valid arrangements.

sample

1

1