In the Fibonacci integer sequence, F0 = 0, F1 = 1, and Fn = Fn − 1 + Fn − 2 for n ≥ 2. For example, the first ten terms of the Fibonacci sequence are: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, … An alternative formula for the Fibonacci sequence is . Given an integer n, your goal is to compute the last 4 digits of Fn. 输入 The input test file will contain multiple test cases. Each test case consists of a single line containing n (where 0 ≤ n ≤ 1,000,000,000). The end-of-file is denoted by a single line containing the number −1. 输出 For each test case, print the last four digits of Fn. If the last four digits of Fn are all zeros, print ‘0’; otherwise, omit any leading zeros (i.e., print Fn mod 10000). 样例输入复制 0 9 1000000000 -1 样例输出复制 0 34 6875

抱歉，由于您的问题和之前的问题类似，我可能误解了您的问题。ChitGPT不能直接读取输入输出，需要在代码中进行处理。以下是 Python 代码实现：

import sys

MOD = 10000

def matrix_mul(a, b):
    c = [[0] * 2 for _ in range(2)]
    for i in range(2):
        for j in range(2):
            for k in range(2):
                c[i][j] += a[i][k] * b[k][j]
                c[i][j] %= MOD
    return c

def matrix_pow(a, n):
    res = [[1, 0], [0, 1]]
    while n:
        if n & 1:
            res = matrix_mul(res, a)
        a = matrix_mul(a, a)
        n >>= 1
    return res

for line in sys.stdin:
    n = int(line.strip())
    if n == -1:
        break
    if n == 0:
        print(0)
    else:
        a = [[1, 1], [1, 0]]
        res = matrix_pow(a, n - 1)
        print("{:04d}".format(res[0][0] % MOD))

对于每个输入的 n，我们先判断是否为 0，如果是，直接输出 0；否则，使用矩阵快速幂算法求出 F(n)，然后输出 F(n) mod 10000，格式化字符串保证输出为 4 位数字。