算法 Plan

Qingdao Institute of Technology is the highest academic institution in Jiaozhou, so it has extremely strict discipline. In order to get a good grades, Li had to prepare a review route in advance to cope with the fianl exam. There are n liberal arts exams in this semester, and there are 4 exam subjects, namely politics, history, geography and comprehensive course . Every time you take a test but it is uncertain, so Li don't know which course to review before the exam. He hopes to predict the exams that may be tested next time. So he collected information in previous liberal arts exams. From the previous exams, he discovered several rules:

If the test is political, then the next time you will test the history;
If the test is comprehensive course, then the next time you will test the geography;
If the test is history, then the next time you will take politics or geography;
If the test is geography, then the next time you either take history or the comprensive course. Li already knows that the first exam in this semester is political. He intends to develop an exam review plan that can address all possible situations. Therefore, he would like to know how many possible test subjects are arranged throughout the semester to meet the above rules.
输入格式:
A positive integer n represents the total number of exams for the semester. The input data is guaranteed to be n<=10000.

输出格式:
A positive integer indicating the total number of subject arrangements for the rule. Considering that this result can be very large, you only need to output the value of mod 7654321.

输入样例:
5
输出样例:
5

import sys
#修改默认最大递归深度
sys.setrecursionlimit(1000000)

def fun(n):
    if li[n] != 0:
        return li[n]
    else:
        li[n] = fun(n-1) % 7654321 + fun(n-2) % 7654321
        return li[n]

if __name__ == "__main__":
    li = [0 for n in range(10001)]
    li[0] = li[1] = li[2] = 1
    n = int(input())
    print(fun(n) % 7654321)