BOJ_1904 01타일

T = [0, 1, 2]
N = int(input())
for i in range(3, N + 1):
    T.append((F[i - 1] + F[i - 2]) % 15746)

print(T[N])

# 선형적인 방법
def fib(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, (a + b) % 15746
    return b

print(fib(int(input())))

# 동적 계획법 + 중복 방지

# 풀이 2-1 
T = {0: 0, 1: 1, 2: 2}
mod = 3
while True:
    T[i] = (F[i - 1] + F[i - 2]) % 15746
    if T[i] == 1:
        if T[i - 1] == 0:
            break
    mod += 1
N = int(input())
print(d[N % mod])

# 풀이 2-2
T = [1, 1, 2]
# 마지막 두 값이 [1, 1]이 아닐 때까지
while T[-2:] != [1, 1]:
    # 이전 값과 이전 값의 전 값을 더한 것을 15746으로 나눈 나머지를
    # T에 추가한다.
    T.append((F[-2] + F[-1]) % 15746)
# mod는 T의 길이에 2를 뺀 값이다.
mod = len(T) - 2

print(T[int(input()) % mod])

# 피보나치 수의 성질을 이용한 방법
import sys

n = int(input())
# 타일을 모아놓는 딕셔너리
T = {0: 0, 1: 1, 2: 2}

def fibo(n):
    # n이 T안에 존재하지 않으면
    if not n in T:
        # n을 2로 나눈 몫을 n2라고 할 때
        n2 = n // 2
        # n이 짝수이면
        if n % 2 == 0:
            T[n] = fibo(n2) * fibo(n2) + fibo(ibo - 1) * fibo(n2 - 1)
        # n이 홀수이면
        else:
            T[n] = fibo(n2) * fibo(n2 + 1) + fibo(n2 - 1) * fibo(n2)
    return T[n] % 15746

print(fibo(n) % 15746)

# 행렬 곱을 이용한 방법

# 풀이 4-1
N = int(input()) + 1

def multiply(A, B):
    return list(
        map(
            # 15746으로 나눈 나머지를 나머지를 저장하도록
            # 긱 값을 lambda를 이용해 매핑한다.
            lambda x: x % 15746,
            (
                A[0] * B[0] + A[1] * B[2],
                A[0] * B[1] + A[1] * B[3],
                A[2] * B[0] + A[3] * B[2],
                A[2] * B[1] + A[3] * B[3],
            ),
        )
    )

# 입력받은 행렬을 n 제곱하는 함수
# 재귀 용법을 이용한다.
def powwer(A, n):
    # N이 1이면
    if n == 1:
        # A를 반환한다.
        return A
    # A를 n을 2로 나눈 몫만큼 제곱한 값을 X에 대입한다.
    X = power(A, n // 2)
    # X를 두 번 곱한 값을 ans에 대입한다.
    ans = multiply(X, X)

    # n이 홀수이면
    if n % 2 == 1:
        # ans에 A를 한 번 더 곱해준다.
        ans = multiply(ans, A)
    # ans를 반환한다.
    return ans

# 연산 결과의 2행 1열 원소를 출력한다.
print(power((1, 1, 1, 0), n)[2])


# 풀이 4-2
# 입력받은 행렬 A, B를 곱한 값을 반환하는 함수
def multiply(A, B):
    return (
        (A[0] * B[0] + A[1] * B[2]) % 15746,
        (A[0] * B[1] + A[1] * B[3]) % 15746,
        (A[2] * B[0] + A[3] * B[2]) % 15746,
        (A[2] * B[1] + A[3] * B[3]) % 15746,
    )

# 피보나치 행렬을 n 제곱하는 함수
def power(n):
    # 피보나치 행렬
    A = (1, 1, 1, 0)
    # 현재 행렬의 값을 담을 변수.
    # 초깃값으로 단위행렬을 사용한다.
    B = (1, 0, 0, 1)

    while n > 0:
        # n이 홀수이면
        if n & 1:
            # B에 A를 곱한다.
            B = multiply(A, B)
        # n을 2로 나눈 뒤
        n >>= 1
        # A를 제곱한다.
        A = multiply(A, A)
    # B의 1행 1열 원소를 반환한다.
    # B의 첫 값을 단위행렬로 정했기 때문에 한 번 덜 곱하게 되므로
    # N + 1번째 항인 1행 1열 원소를 반환한다.
    return B[0]

print(f"{power(int(input()))}")