MOD = 10**9 + 7 def multiply(a, b): return [ [(a[0][0] * b[0][0] + a[0][1] * b[1][0]) % MOD, (a[0][0] * b[0][1] + a[0][1] * b[1][1]) % MOD], [(a[1][0] * b[0][0] + a[1][1] * b[1][0]) % MOD, (a[1][0] * b[0][1] + a[1][1] * b[1][1]) % MOD] ] def matrix_power(matrix, power): result = [[1, 0], [0, 1]] # Identity matrix while power > 0: if power % 2 == 1: result = multiply(result, matrix) matrix = multiply(matrix, matrix) power //= 2 return result def fibonacci(n): if n == 0: return 0 elif n == 1: return 1 mat = matrix_power([[1, 1], [1, 0]], n - 1) return mat[0][0] n = int(input()) if n == 1: print(1) elif n == 2: print(1) elif n == 3: print(3) else: if n % 2 == 0: m = n // 2 print(fibonacci(m + 1) % MOD) else: m = (n - 1) // 2 print(fibonacci(m + 2) % MOD)