可以使用矩阵快速幂加速递推，具体做法过程见 P1083 汉诺塔 Solution

Python 代码（数据使用 C++ std 制造，不再放出）

MOD = 998244353  # 定义模数

# 定义矩阵 A
A = [
    [1, 1, 1],
    [1, 0, 0],
    [0, 1, 0]
]

# 定义初始向量 [F(2), F(1), F(0)] = [1, 1, 1]
initial_vector = [1, 1, 1]

def mat_mult(A, B):
    """矩阵乘法，并对每个元素进行取模"""
    # A 是 3x3 矩阵，B 是 3x1 向量
    result = [0] * 3
    for i in range(3):
        for j in range(3):
            result[i] += A[i][j] * B[j]
            result[i] %= MOD  # 每步都取模
    return result

def mat_pow(A, power):
    """矩阵快速幂，并对每个元素进行取模"""
    # 初始化单位矩阵
    result = [[1 if i == j else 0 for j in range(3)] for i in range(3)]
    base = A

    while power:
        if power % 2 == 1:
            result = mat_mult_matrix(result, base)
        base = mat_mult_matrix(base, base)
        power //= 2

    return result

def mat_mult_matrix(A, B):
    """矩阵乘法，返回 A * B，并对每个元素进行取模"""
    result = [[0] * 3 for _ in range(3)]
    for i in range(3):
        for j in range(3):
            for k in range(3):
                result[i][j] += A[i][k] * B[k][j]
                result[i][j] %= MOD
    return result

def calculate_F(n):
    if n == 0:
        return 0
    elif n == 1 or n == 2 or n == 3:
        return 1
    
    # 使用矩阵快速幂来计算 A^(n-3)
    A_n_minus_2 = mat_pow(A, n - 3)

    # 计算 F(n) = A^(n-3) * [F(3), F(2), F(1)]^T
    result_vector = mat_mult(A_n_minus_2, initial_vector)
    
    # 返回 F(n)
    return result_vector[0]

# 输入n并输出F(n)
n = int(input())
print(calculate_F(n))