from __future__ import annotations







def     A__	(       __A ,			__A ,			__A						):







    '''simple docstring'''
    assert (
        c % greatest_common_divisor(__A ,			__A						) == 0
    )  # greatest_common_divisor(a,b) function implemented below
    ((_lowerCamelCase)    ,				(_lowerCamelCase)    ,				(_lowerCamelCase))  :		List[str]			    =    extended_gcd(__A ,			__A						)  # extended_gcd(a,b) function implemented below
    _lowerCamelCase  :		Optional[Any]			    =    c / d
    return (r * x, r * y)







def     A__	(       __A ,			__A ,			__A ,			__A = 2						):







    '''simple docstring'''
    ((_lowerCamelCase)    ,				(_lowerCamelCase))  :		List[str]			    =    diophantine(__A ,			__A ,			__A						)  # Initial value
    _lowerCamelCase  :		List[str]			    =    greatest_common_divisor(__A ,			__A						)
    _lowerCamelCase  :		Any			    =    a // d
    _lowerCamelCase  :		Any			    =    b // d

    for i in range(__A						):
        _lowerCamelCase  :		Optional[Any]			    =    xa + i * q
        _lowerCamelCase  :		int			    =    ya - i * p
        print(__A ,			__A						)







def     A__	(       __A ,			__A						):







    '''simple docstring'''
    if a < b:
        _lowerCamelCase    ,				_lowerCamelCase  :		str			    =    b, a

    while a % b != 0:
        _lowerCamelCase    ,				_lowerCamelCase  :		int			    =    b, a % b

    return b







def     A__	(       __A ,			__A						):







    '''simple docstring'''
    assert a >= 0 and b >= 0

    if b == 0:
        _lowerCamelCase    ,				_lowerCamelCase    ,				_lowerCamelCase  :		Optional[int]			    =    a, 1, 0
    else:
        ((_lowerCamelCase)    ,				(_lowerCamelCase)    ,				(_lowerCamelCase))  :		Union[str, Any]			    =    extended_gcd(__A ,			a % b						)
        _lowerCamelCase  :		int			    =    q
        _lowerCamelCase  :		Any			    =    p - q * (a // b)

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

    return (d, x, y)


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

    testmod(name="diophantine", verbose=True)
    testmod(name="diophantine_all_soln", verbose=True)
    testmod(name="extended_gcd", verbose=True)
    testmod(name="greatest_common_divisor", verbose=True)





from __future__ import annotations

import sys







def     A__	(       __A						):







    '''simple docstring'''
    if n < 0:
        raise ValueError("""Negative arguments are not supported"""						)
    return _fib(__A						)[0]







def     A__	(       __A						):







    '''simple docstring'''
    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
    _lowerCamelCase    ,				_lowerCamelCase  :		List[Any]			    =    _fib(n // 2						)
    _lowerCamelCase  :		List[Any]			    =    a * (b * 2 - a)
    _lowerCamelCase  :		Optional[int]			    =    a * a + b * b
    return (d, c + d) if n % 2 else (c, d)


if __name__ == "__main__":
    lowerCAmelCase      :				Union[str, Any]     			=int(sys.argv[1])
    print(F"""fibonacci({n}) is {fibonacci(n)}""")




