"""simple docstring"""







from __future__ import annotations


def   a__      (		UpperCAmelCase__       :			Optional[int]		,			UpperCAmelCase__       :			List[Any]		,			UpperCAmelCase__       :			str			)->	int:
						assert n > 1 and a > 0 and greatest_common_divisor(UpperCAmelCase__		,			UpperCAmelCase__			) == 1
						((UpperCAmelCase__)	,      (UpperCAmelCase__)	,      (UpperCAmelCase__))						=		extended_gcd(UpperCAmelCase__		,			UpperCAmelCase__			)  # Implemented below
						UpperCAmelCase__						=		(b * s) % n
						return x


def   a__      (		UpperCAmelCase__       :			Union[str, Any]		,			UpperCAmelCase__       :			Tuple			)->	int:
						((UpperCAmelCase__)	,      (UpperCAmelCase__))						=		extended_euclid(UpperCAmelCase__		,			UpperCAmelCase__			)  # Implemented below
						if b < 0:
												UpperCAmelCase__						=		(b % n + n) % n
						return b


def   a__      (		UpperCAmelCase__       :			Tuple		,			UpperCAmelCase__       :			Dict		,			UpperCAmelCase__       :			Optional[int]			)->	int:
						UpperCAmelCase__						=		invert_modulo(UpperCAmelCase__		,			UpperCAmelCase__			)
						UpperCAmelCase__						=		(b * s) % n
						return x


def   a__      (		UpperCAmelCase__       :			List[Any]		,			UpperCAmelCase__       :			str			)->	tuple[int, int, int]:
						assert a >= 0 and b >= 0

						if b == 0:
												UpperCAmelCase__	,      UpperCAmelCase__	,      UpperCAmelCase__						=		a, 1, 0
						else:
												((UpperCAmelCase__)	,      (UpperCAmelCase__)	,      (UpperCAmelCase__))						=		extended_gcd(UpperCAmelCase__		,			a % b			)
												UpperCAmelCase__						=		q
												UpperCAmelCase__						=		p - q * (a // b)

						assert a % d == 0 and b % d == 0
						assert d == a * x + b * y

						return (d, x, y)


def   a__      (		UpperCAmelCase__       :			Optional[Any]		,			UpperCAmelCase__       :			Any			)->	tuple[int, int]:







						if b == 0:
												return (1, 0)
						((UpperCAmelCase__)	,      (UpperCAmelCase__))						=		extended_euclid(UpperCAmelCase__		,			a % b			)
						UpperCAmelCase__						=		a // b
						return (y, x - k * y)


def   a__      (		UpperCAmelCase__       :			List[Any]		,			UpperCAmelCase__       :			int			)->	int:







						if a < b:
												UpperCAmelCase__	,      UpperCAmelCase__						=		b, a

						while a % b != 0:
												UpperCAmelCase__	,      UpperCAmelCase__						=		b, a % b

						return b


if __name__ == "__main__":
						from doctest import testmod

						testmod(name="""modular_division""", verbose=True)
						testmod(name="""modular_division2""", verbose=True)
						testmod(name="""invert_modulo""", verbose=True)
						testmod(name="""extended_gcd""", verbose=True)
						testmod(name="""extended_euclid""", verbose=True)
						testmod(name="""greatest_common_divisor""", verbose=True)





"""simple docstring"""







from __future__ import annotations

import sys


def   a__      (		UpperCAmelCase__       :			int			)->	int:
						if n < 0:
												raise ValueError("""Negative arguments are not supported"""			)
						return _fib(UpperCAmelCase__			)[0]


def   a__      (		UpperCAmelCase__       :			int			)->	tuple[int, int]:
						if n == 0:  # (F(0), F(1))
												return (0, 1)

						# F(2n) = F(n)[2F(n+1) − F(n)]
						# F(2n+1) = F(n+1)^2+F(n)^2
						UpperCAmelCase__	,      UpperCAmelCase__						=		_fib(n // 2			)
						UpperCAmelCase__						=		a * (b * 2 - a)
						UpperCAmelCase__						=		a * a + b * b
						return (d, c + d) if n % 2 else (c, d)


if __name__ == "__main__":
						UpperCamelCase_       :       int							   =		int(sys.argv[1])
						print(F"""fibonacci({n}) is {fibonacci(n)}""")

